数据结构之二分查找

本文是数据结构和算法之美的学习笔记

二分查找是一种非常简单易懂的快速查找算法，生活中到处可见。比如有一个0-99之间的数组，随便取一个数，每猜一次都告诉你大了还似乎小了直到猜中为止。比如这个数是33

第一次 0-99 中间数是49 49>33

第二次 0-48 中间数是24 24<33

第三次 25-48 中间数是36 36>33

第四次 25-35 中间数是30 30<33

第五次 31-36 中间数是33 33=33

只需要5次就找到了

二分查找针对的是一个有序的数据集合，每次都通过根区间内的中间元素对比，将待查找的区间缩小为之前的一半，知道招到查找的元素，或者区间缩小为 0。

最简单的二分查找实现：

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;
}

之所以是最简单的实现，因为限制很多， 必须是有序的数组并且不能有重复的元素 。

循环退出条件

low<=high

mid的取值

mid=(low+high)/2这种写法有问题。因为low和high比较大的话，两者之和有可能会溢出。改进的方法是low+(high-low)/2。更近一步的话可以使用位运算符，因为计算机处理位运算符比除法快，low+((high-low)>>1)

low和high的更新

low=mid+1 heigh=mid-1 如果直接写low=mid 或者 high=mid可能会发生死循环。比如high=3,low=3，如果a[3]不等于value，就死循环了。

二分查找除了使用循环实现，还可以使用递归，因为其子任务都是找到中间的值跟要找的值做比较

// 二分查找的递归实现
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);
  }
}

二分查找的局限性

（1）二分查找依赖的是顺序表结构，简单点就是数组。不能依赖链表，主要原因是二分查找算法需要按照下标随机访问元素。我们知道，按照下标随机访问数据的时候，链表比数组耗时，也会导致二分查找的时间复杂度高。

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

如果不是有序的，必须得先 排序 在查找。二分查找只能用在插入和删除操作不频繁，一次排序多次查找的场景中，或者直接就是静态的数据，对于动态变化的数据集，二分查找并不适用。

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

数据量太小的话直接遍历就行了，不过如果比较的时候比较耗时，这时候还是用二分查找比较好，可以减少比较的次数。

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

因为二分查找底层需要依赖数组这种数据结构，而数组为了支持随机访问，对内存的连续性要求比较高。如果数组都存不下了那也就没有查找了。

思考：使用二分法求一个数的平方根，精确到小数点后6位

//x位输入的数 precision为精确度比如0.000001
public double sqrt(double x, double precision) {
        if(x == 0 || x == 1){
            return x;
        }
        double low = 0;
        double high = x;
        double mid = low + (high - low)/2;
        while(Math.abs(high - low )> precision) {
            if (mid * mid > x ) {
                high = mid;
            } else if (mid * mid < x) {
                low = mid;
            } else {
                return mid;
            }
            mid = low + (high - low)/2;
        }
        return mid;
    }

上面的二分查找是最简单的二分查找，数据中没有重复的数据，如果数组中有重复的数据，使用上面的二分查找就可能会出错了

比如查找第一个等于给定值的元素，使用下面一组数据 1,2,3,4,5,8,8,8,11,16

如果使用上面的查找方法，我们找到的是第三个8，而正确的结果应该是第一个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 if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}

当a[mid]等于要查找的元素的时候，需要判断一下是不是第一个给定的值，如果mid为0那他已经是数组的第一个元素，肯定是我们要找的，如果不为0但是它前面的一个元素不等于value也是我们要找的，如果一样那说明不是我们要找的更新high值为high=mid-1

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

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) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

如果a[mid]小于小于要找的value,那么值肯定在mid+1到high之间

如果a[mid]大于要查找的值，就看看它是不是第一个元素，或者它前面的元素是不是大于等于value值