二分查找

2019-02-18

之前在bilibili看到一个有趣的视频，关于二分查找的。戳我看这个有趣的视频

此文是学习《数据结构与算法之美》时的笔记。

二分思想

就如上面视频中的栗子，猜数字游戏，如果从头开始一个一个的猜是非常低效的。

在实际的开发场景中，假设有1w条订单数据，已经按照订单的金额从小到大排序，每个定干的金额不同，最小单位是元。

如果从第一个订单开始，遍历这1w条订单，直到找到目标为止，这种方法在最坏情况下可能要便利完所有数据才能找到。

但是用二分法，每次都通过跟区间中间元素对比，将整个带查找的区间缩小为之前的一半，直到查找的需要的数据或者区间缩小为0。

二分查找实现(递归和非递归)

// 非递归实现
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;
    }
  }/*while*/

  return -1;
}

循环退出条件：low<=high
mid的取值：mid=(low+high)/2在low和high比较大的话两者之和容易溢出。

改进：low+(high-low)/2

更高效：low+((high-low)>>1)

low和high的更新

low=mid+1和high=mid-1这里的+1和-1，如果写成low=mid或high=mid就可能发生死循环。

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

int b(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);
  }
}

时间复杂度

二分查找的被查找区间缩小速度是一个等比数列，公比q为1/2。

假设数据规模为n，每次查找后数据规模都会缩小为原来的一半，最坏情况下，直到查找区间被缩小为空停止。

n/2^k=1时，k就是总共缩小的次数，每次缩小只涉及2个数据的比较，经过k次区间缩小操作，时间复杂度为O(k)。k等于以2为底n的对数，解得时间复杂度为O(logn)。

O(logn)在某些情况下比O(1)时间复杂度的算法高效。O(1)时忽略掉常熟、系数和低阶。当数据规模够大时，如O(10000)，此时log(n)的算法效率比O(1)的高。

局限性

二分查找依赖顺序结构
二分查找针对的是有序数据
数据量太小不适合二分查找

比如在10个元素的数组中查找一个元素，遍历会来的更方便一些。而且查找速度也差不多。
数据量太大也不适合二分查找

为了支持随机访问，内存空间需要连续。

二分查找的变体问题

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

当区间中间值不等于要查找的元素时，需要继续查找。

当区间中间值等于要查找的元素时，看看中间值的前一个值是否等于要查找的元素，如果等则更新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) {
      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;
}

查找最后一个值等于给定值的元素

跟第一种一样，不过这次要和mid后面的一个元素进行比较。更新low=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) {
      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;
}

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

如果mid的值小于要查找的值，则目标值在[mid+1,high]之间，更新low。

如果mid的值大于要查找的值，目标值在[low,mid-1]之间，更新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) >> 1);
    if (a[mid] >= value) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

查找最后一个小于等于给定值的元素

要查找的值大于当前mid中的值，目标值在[low,mid-1]之间，更新high=mid-1。

要查找的值小于mid+1的值，则要查找的值在[mid+1,high]之间，更新low=mid+1。

public int bsearch7(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 ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

数据结构与算法之美