二分法查找算法

   二分法查找具有惊人的查找速度，尤其是对于海量数据的时候，作用更加明显，时间复杂度用大O表示法，即是（logn），这种（logn）时间复杂度是非常神奇的，比如 n 等于 2 的 32 次方，这个数很大了吧？大约是42亿，也就是说，如果我们在 42 亿个数据中用二分查找一个数据，最多需要比较 32 次。

  但是，二分查找是有局限性的：

（1）二分查找依赖的是顺序表结构，简单点说就是数组。

解释：主要原因是二分查找算法需要按照下标随机访问元素。

（2）二分查找针对的是有序数据。

（3）数据量太小不适合二分查找。

（4）数据量太大也不适合二分查找。

解释：二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的空间要求比较苛刻。比如，我们有1GB的数据，那就需要1GB内存空间。

接下来是二分算法的代码了：

//二分法查找给定值 普通Java实现
public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;

  while (low <= high) {
    int mid = (low + high) / 2;
    if (a[mid] == value) {
      return mid;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {
  return bsearchInternally(a, 0, n - 1, val);
}

private int bsearchInternally(int[] a, int low, int high, int value) {
  if (low > high) return -1;

  int mid =  low + ((high - low) >> 1);
  if (a[mid] == value) {
    return mid;
  } else if (a[mid] < value) {
    return bsearchInternally(a, mid+1, high, value);
  } else {
    return bsearchInternally(a, low, mid-1, value);
  }
}

    //查找第一个值等于给定值的元素
    public int bsearch1(int[] a, int n, int value){
        int low = 0;
        int high = n - 1;
        
        while(low <= high){
            //这里用到的(右移)>>运算符  右移运算符简单理解就是 除以2的移动次幂 下面这个就是 等同于(high-low)/2^1
            int mid = low + ((high-low) >> 1);
            if(a[mid] > value){
                //说明value 在前半部分 把排好序的数组 从中间一切两半
                high = mid - 1;
            }else if(a[mid] < value){
                //说明value 在后半部分
                low = mid + 1;
            }else{
                //a[mid] == value
                //但是我们要查找的是第一个 等于改定值的元素 还需要确认一下a[mid] 是不是第一个
                if(mid == 0 || a[mid - 1] != value){
                    //当mid == 0 的时候，说明这是第一个元素，肯定是我们要找的
                    //当a[mid] 前面的元素不等于 value的时候，说明a[mid]肯定就是第一个等于给定值的元素
                    //因为该数组是有序的，这里就是默认从小到大排序
                    return mid;
                }else{
                    high = mid - 1;
                }
            }
        }
        //这个 -1 代表的就是没有找到
        return -1;
    }
    
    //查找最后一个值等于给定元素
    public int bsearch2(int[] a, int n, int value){
        int low = 0;
        int high = n - 1;
        
        while(low <= high){
            int mid = low + ((low+high) >> 1);
            if(a[mid] > value){
                high = mid - 1;
            }else if(a[mid] < value){
                low = mid + 1;
            }else{
                if(mid == n-1 || a[mid+1] != value){
                    //同理
                    return mid;
                }else{
                    low = mid + 1;
                }
            }
        }
        return -1;
    }
    
    //查找第一个大于等于给定值的元素
    public int bsearch3(int[] a, int n, int value){
        int low = 0;
        int high = n - 1;
        
        while(low <= high){
            int mid = low + ((low+high) >> 1);
            if(a[mid] >= value){
                if(mid == 0 || a[mid-1] < value){
                    //a[mid] 是第一个数，但是a[mid]大于等于value的数，所以肯定就是它了
                    //a[mid - 1] 是小于 value 的数，它的前一个数是小于value的，肯定也是它了
                    return mid;
                }else{
                    high = mid - 1;
                }
            }else{
                low = mid + 1;
            }
        }
        return -1;
    }
    
    //查找最后一个小于等于给定值得元素
    public int bsearch4(int[] a, int n, int value){
        int low = 0;
        int high = n -1;
        
        while(low <= high){
            int mid = low + ((low+high) >> 1);
            if(a[mid] > value){
                high = mid - 1;
            }else{
                if(mid == n-1 || a[mid+1] > value){
                    //同理
                    return mid;
                }else{
                    low = mid + 1;
                }
            }
        }    
        return -1;
    }