基本思想

二分查找算法的基本思想就是:

• 在一个有序的(默认我们都是升序，如果是降序后面的条件置反即可)数组中;
• 将要查找的值和数组中间的那个元素比较;
• 如果要找的数大于中间的元素,就从中间的元素后一个元素开始到数组最后一个元素这个区间里面继续寻找;
• 如果要找的数小于中间的元素,就从0开始到此时的中间的元素这个区间内继续寻找;
• 如果它们相等，那么此时我们要找的元素就是当前中间的元素，直接返回下标即可。

java代码实现

private int binarySearch(int[] arr,int k){        int index = -1;        int start = 0;        int end = arr.length;        while (start < end){            //  这里有可能会溢出，有两种解决方案            //  1、 修改为 start+(end-start)/2            //  2、 通过位移操作，这样也可以完成除2，在jdk源码中使用的是这种方法            int mid = (end + start) / 2;            //  如果小于中间的元素就从0开始到当前中间的下标这个区间里面继续寻找            if (k < arr[mid]){                end = mid;            //  如果大于中间的元素就从当前的下标到最后一个元素这个区间里面继续寻找            }else if (k > arr[mid]){                start = mid + 1;            //  如果等于中间的元素就说明当前元素就是我们要找的下标            }else {                return mid;            }        }        //  如果循环结束了都没找到说明这个数组里面没有我们要找的元素        return -1;    }

时间复杂度分析

• 最好的情况是我们要找的就是中间那个,此时的时间复杂度为O(1);
• 最坏的情况是我们找完最后一趟才找到甚至没有找到,这个时候的时间复杂度为O(logN);