1、二分查找概念　　

1.1、核心思想　　

　　二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

　　二分查找的时间复杂度是 O(logn)，当数据量较大时，O(logn) 往往优于常量时间复杂度 O(1)，例如：2的32次方，大约是42亿也只需要32次查找，但是常量级可能是 O(1000)甚至更大。所以 O(logn)是一种很高效的算法实现。

1.2、二分查找的局限性

　　• 针对的是线性表结构，简单说就是数组

　　　　比如链表也不能使用二分查找，主要二分查找需要按照下标随机访问元素。

　　• 针对的是有序数据

　　• 不能数据量太大的数据

　　　　因为二分查找针对有序数组，但是数组是连续的，对于内存的要求较高。

2、简单二分查找的实现

　　简单二分查找可以通过递归和非递归两种方式实现。简单二分查找假设数组中没有重复元素。

2.1、非递归方式

private int bsearch(int[] nums,int value){
        int low = 0;
        int high = nums.length-1;
        //1、终止条件
        while (low <= high){
            //2、计算中间位置
            int mid = low + ((high-low) >> 1);
            if (nums[mid] == value){
                return mid;
            }
            //3、更新范围
            else if (nums[mid] > value){
                high = mid-1;
            }else {
                low = mid+1;
            }
        }
        return -1;
    }    

这里有几点注意的：

　　1、终止条件

　　　　终止条件是 low <= high，而不是low < high

　　2、计算中间位置 mid

　　　　经常会写 mid = (low+high) / 2，这么写不太严谨，因为如果 low 和 high 足够大的话相加可能会溢出，可以写成 mid = low + (high-low) / 2。更高效点就是上面那种写法，因为计算机处理位运算更快。

　　3、范围更新

　　　　更新范围时要更新到 mid 的下一位或上一位，high = mid-1 或 low = mid+1。不要写成 high = mid 或 low = mid，这样可能造成死循环。

2.2、递归方式

    private int recurBsearch(int[] nums,int value){
        return recur(nums,0,nums.length-1,value);
    }

    private int recur(int[] nums,int low,int high,int value){
        //终止条件
        if (low > high)return -1;
        //计算中间位置
        int mid = low + ((high-low) >> 1);
        if (nums[mid] == value){
            return mid;
        }else if (nums[mid] > value){
            return recur(nums,low,mid-1, value);
        }else {
            return recur(nums,mid+1,high,value);
        }
    }

3、二分查找的变形

　　二分查找的变形有很多种，我们看几种比较经典的变形案例。

3.1、查找第一个值等于给定值的元素

　　来举一个例子：从数组 a[10]{1,3,4,5,6,8,8,8,11,18} 中查找第一个等于8的位置。有些解题代码很简洁，但是很难理解：

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid = low + ((high - low) >> 1);
    if (a[mid] >= value) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  if (low < n && a[low]==value) return low;
  else return -1;
}

　　这段代码的逻辑就很难理解，如果死记硬背的话过几天可能就忘了。