java 数据结构学习之（一）数组
数组是应用最广泛的数据结构，也是最简单的数据结构，它有着结构简单，算法通俗易懂的优点。数组又分为有序数组和无序数组，我们通常用的都是无序数组。下面是这两种数组之间的区别
?
无序数组的优点：插入快，根据索引查找快。缺点：在未知数组位置的情况下查找慢，删除慢。
有序数组的优点：使用二分法查找快。缺点：插入数据和删除数据慢。因为插入数据要做排序操作。
?
综合以上，可以看出他们各自的使用场景，无序数组适合经常做插入操作和用索引访问的环境，而有序数组更趋向于随机查找。
?
下面是封装的一个数组类，扩展了了insert,delete,find方法,有许多不足之处，比如insert方法没有判断数组界限。懒得搞了。
?
?怎么样，是不是数据量越大查找次数的优势就越大，比如在10000里查找一个元素，线性查找需要的平均次数是1000/2 = 5000次， 而二分查找法的计算公式是以二为基数的对数 ，所谓对数就是指数的反函数 ，一般计算器的log函数就是以10为基数的对数，那么计算10000的二分查找法所需次数的公式就是log(10000) * 3.322 ，乘以3.322是因为要将该结果从10的基数转换成2的基数，这样下来四舍五入差不多就是所需次数了。结果是 13.288 取整就是14次。5000比14可想而知效率高了多少。ps:也可以这样计算log2(x) = log(x) / log(2)??
?
下面是二分法查找的基本步骤（假如是数组元素升序排序的）
1.将需查找元素和数组中间的元素比较，如果相等则返回，如果数组中间元素比需查找元素大则说明目标元素的位置在中间元素的前面，反之在后面。
2.通过步骤1，已经缩小了一半的范围，然后重复步骤1，直到找到元素或者找不到元素为止，就算找不到也最多就是查找Math.ceil(log(数据长度）* 3.322 )次。
?
?
这有点象我们平常的猜数游戏
java代码二分法实现?
?
?
就是二分法这样逐渐缩小查询范围的原理来实现的。
?
下面是一个用二分法实现了find,delete,insert方法的数组类
?
public void insert(int c){int lowerBound = 0,upperBound = nElement -1,max = nElement;while(lowerBound <= upperBound ){//用二分法查找在数组中第一个比c大的元素int middle = (lowerBound + upperBound)/2;if(arr[middle] == c){max = middle;break;}else if(arr[middle] > c){max = middle;upperBound = middle - 1;}else{lowerBound = middle + 1;}}//移动数组for (int i = nElement; i > max; i--) {arr[i] = arr[i - 1];}arr[max] = c;nElement++;}/**将两个有序的数组合并成一个有序的数组 * @param src1 * @param src2 */public void mearge(int[] src1,int[] src2){int[] tar = new int[src1.length + src2.length];for (int i = 0,k=0,j=0; i < tar.length; i++) {if(j >= src2.length || (k < src1.length && src1[k] < src2[j])){tar[i] = src1[k++];}else{tar[i] = src2[j++];}}for (int i = 0; i < tar.length; i++) {System.out.println(tar[i]);}}public boolean delete(int c){int index = find(c);if(index != nElement--){for (int i = index; i < nElement; i++) {arr[i] = arr[i + 1];}return true;}else{return false;}}public int[] getArr(){return this.arr;}public void display(){for (int i = 0; i <nElement; i++) {System.out.println(arr[i]);}}/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stubOrderArray h1 = new OrderArray(12);for (int i = 0; i < 12; i++) {h1.insert((int)(Math.random() * 1000));}//h1.display();OrderArray h2 = new OrderArray(10);for (int i = 0; i < 10; i++) {h2.insert((int)(Math.random() * 1000));}h1.mearge(h1.getArr(), h2.getArr());//System.out.println(h.find(34));}}?
这就是对数组的二分查找法基本的学习。
