Java数据结构-有序数组的二分查找法解读

---

一、二分查找法

二分查找法（binary search）是一种思想，当需要在一段有序的数据中（升序或者降序）中查找某个数据时，如在一个形如1,2,3,4，···，99,100的数组中判断60是否存在，最简单的方式就是遍历判断：

for(int i = 0;i < array.length;i ++){
	if(array[i] == 60){
	 	System.out.println(“存在”);
	}
}

对于100个数据来说，最坏的情况就是查找比对100次，但是随着元素的扩充，查找的时间会越来越长，比对的时间也会越来越长，所以这时，二分查找法这种思想出现了：
每次都“猜测”一个数据范围段中的中间值，如果这个值比我们需要查询的数大，那么说明我们需要的值在这个中值的左边区域，即将查找的范围缩小的一半，同理，如果这个中值小于我们所需的查询值，那么我们要查的值就在右半部分，通过这种思想，每次查询都能排除掉1/2的数据，这就是二分查找法。

 public void binarySearch(int[] array,int searchkey){
        int lowerBound= 0;
        int upperBound= array.length - 1;
        while(true){
            int currentIndex = (lowerBound + upperBound)/2;
            if(array[currentIndex] == searchkey){
                System.out.println("已经找到"+searchkey);
                return;
            }else if(lowerBound > upperBound){
                System.out.println("不存在"+searchkey);
                return;
            }else if(array[currentIndex] != searchkey){
                if(array[currentIndex] > searchkey){
                    //在左半部分，上确界改变
                    upperBound = currentIndex - 1;
                }else{
                    //在右半部分，下确界改变
                    lowerBound = currentIndex + 1;
                }
            }
        }
    }

二、大O表示法

大O表示法是用以估算算法的时间复杂度的一种方法，它用符号O(N)来表示算法执行时间，其中N是一个和元素项相关的表达式的取最高阶，忽略掉了常数项。比如查找长度为10的数组中的某一项时，最多需要查找10次；当长度为100时，最多需要查找100次，假如每一次查找需要消耗时间为k，那么算法执行时间t和数组长度的关系可表示为 t = kn，其中k是常数，n的最高次为1，可不写，那么用大O表示法表示其时间复杂度为O(n);
而二分查找法的时间复杂度可以表示为O(logn)，其中n为元素数；

用大O表示法表示的时间复杂度，O(1)表示的是常数时间操作，这是算法最理想的一种情况，但是绝大多数算法都无法达到这样的效率；二分查找法是时间复杂度为O(logn),算法的执行时间和元素数符合对数增长，是一种很好的情况；而最不理想的情况就是O(n^2)这类的指数型增长了。

三、二分查找法快速估算

使用二分查找法时我们可以发现一些规律，如图


即二分查找法的范围r和查找次数s可以用对数函数s = log2(r)来表示，比如在100个数据中查询一个数据吗，最多需要log2(100) <=7次。