時間復(fù)雜度O(logn)

三個易出錯的地方
退出循環(huán)條件
mid取值
low和high更新

非遞歸

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;

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

  return -1;
}

遞歸

// 二分查找的遞歸實現(xiàn)
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);
  }
}

二分查找依賴數(shù)組
元素要有序
適用于插入封断、刪除操作不頻繁。也就是集合變動不頻繁的
數(shù)據(jù)量太小不適合二分查找帆焕，如果數(shù)據(jù)比較比較耗時也需要使用二分查找
數(shù)據(jù)量太大也不適合二分查找

二分查找的變種

查找第一個等于給定值的元素

    //查找第一個等于給定值的元素
    public static int searchFirstPosition(int[] arr,int key){
        int lo = 0;
        int hi = arr.length - 1;
        while (lo <= hi){
            int mid = lo + ((hi - lo) >> 1);
            if (key > arr[mid]){
                lo = mid + 1;
            } else if (key < arr[mid]){
                hi = mid - 1;
            } else {
                if (mid == 0 || arr[mid - 1] != key){
                    return mid;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }

查找最后一個值等于給定值得元素

    //查找最后一個值等于給定值得元素
    public static int searchLastPostion(int[] arr,int key){
        int lo = 0;
        int hi = arr.length - 1;
        while (lo <= hi){
            int mid = lo + ((hi - lo) >> 1);
            if (key > arr[mid]){
                lo = mid + 1;
            } else if (key < arr[mid]){
                hi = mid - 1;
            } else {
                if (mid == arr.length - 1 || arr[mid + 1] != key){
                    return mid;
                } else {
                    lo = mid + 1;
                }
            }
        }
        return -1;
    }

查找第一個大于給定值的元素

    //查找第一個大于給定值的元素3,4,6,7,10中查找大于等于5的元素，那就是6
    public static int searchFirstBigOrEqualsPosition(int[] arr,int key){
        int lo = 0;
        int hi = arr.length - 1;
        while (lo <= hi){
            int mid = lo + ((hi - lo) >> 1);
            if (key <= arr[mid]){
                if (mid == 0 || arr[mid - 1] < key){
                    return mid;
                } else {
                    hi = mid - 1;
                }
            } else {
                lo = mid + 1;
            }
        }
        return -1;
    }

查找最后一個小于等于給定值的元素

    //查找最后一個小于等于給定值的元素
    public static int searchLastSmallOrEqualsPosition(int[] arr,int key){
        int lo = 0;
        int hi = arr.length - 1;
        while (lo <= hi){
            int mid = lo + ((hi - lo) >> 1);
            if (key >= arr[mid]){
                if (mid == arr.length - 1 || arr[mid + 1] > key){
                    return mid;
                } else {
                    lo = mid + 1;
                }
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

可以用二分查找的解決的問題基本都使用散列表或者二叉樹解決，即便是二分查找在內(nèi)存上更節(jié)省叶雹，那二分查找在實際使用中要用在哪里财饥？答案就是近似值查找，這種二分查找的變種折晦。因為這種近似值查找散列表和二叉樹實現(xiàn)起來都比較難