顺序查找？

所谓顺序查找，就是从第一个元素开始，遍历表中的元素，以找到对应的节点

对于线性表来说， 如果该表是无序表， 那么不管它采用的是顺序存储还是链式存储， 都必须使用顺序查找。

如果该表是有序的，但是采用链式存储， 也必须使用顺序查找

当该表有序且顺序存储时， 我们可以采用二分查找

二分查找？

所谓二分查找就是说，针对一个有序数组，我们先取数组的中间值和要查找的目标值比较，如果比目标值大，就在左边的一半中查找，查找方式还是先取中间值比较。。。

 

 这样对于一个长度为n的有序数组， 查找一个数所花费的时间最多为log2n

如长度为8的数组，最多3次就可以定位到

 1 /**
 2      * 使用二分查找在array数组中查询target的位置
 3      * @param array
 4      * @param startIndex
 5      * @param endIndex
 6      * @param target
 7      * @return
 8      */
 9     private static int binarySearch(int[] array, int startIndex, int endIndex, int target) {
10         int low = startIndex;
11         int high = endIndex-1;
12         while (low<=high) {
13             //取中间
14             int middle = (low + high)>>1;
15             int midValue = array[middle];
16             //如果中间值比target小， 就在右边查找
17             if (midValue < target) {
18                 //移动低位指针到middle+1的位置
19                 //+1是为了避免重复查找，因为Middle位置其实已经比较过了，相等的话就会返回
20                 //另外，如果不加1， 每次都会重复查找一个数据，那么最后剩下2个数据时，如array[10], array[11], 
21                 //要查找array[11], low = 10, high = 11, 那么middle=10，low=middle进入死循环
22                 low = middle+1;
23             } else if (midValue > target) {
24                 //移动高位指针到middle-1的位置
25                 high = middle-1;
26             } else {
27                 return middle;
28             }
29         }
30         //通常返回最后一次查找的低位指针的位置 
31         return -(low+1);
32     }

1 public static void main(String[] args) {
2         int[] array = {4,7,8,10,14,21,22,36,62,77,81,91};
3         int index = binarySearch(array, 0, array.length, 91);
4         System.out.println(index);
5     }

 

网上流传一种说法： 90%的程序员都写不出没有Bug的二分查找

其实这里的问题在于

int middle = (low + high)>>1;

这一行，如果low和high的值很大，可能会有内存溢出的问题 

所以我们修改这一行代码为：
int middle = low + ((high-low)>>1);

注意，由于移位运算的优先级较低， 要用括号括起来