二分查找及其变种实现

?

        二分查找(Binary Search)又叫折半查找,对于已排序的数组,是一种非常高效的排序算法,时间复杂度为O(logn)。二分查找很简单也很高效,但要写好用好二分查找却不容易,多数程序员都不能完整地实现一个无bug的二分查找。

1.最基本的二分查找

        我们先来看一个最基本的二分查找,在一组无重复的数组中查找指定的数并返回数组索引。

int binarySearch(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;
}
二分查找及其变种实现

 容易错的地方:

  • 循环结束条件

        循环结束条件为 low <= high;

        错误写法:low < high,low < high可能会导致死循环,边界判断很重要;

  • 中间位置的计算

        中间位置的计算可以写作 mid = (low+high)/2 或者 mid = low+(high-low)/2。但前者的问题是low和high比较大时low+high可能会溢出,超出int表达的最大范围。如果有对性能的极致要求,还可以把除2改为位运算,写作mid=low+((high-low)>>1),位运算的性能要比除法好很多。

        错误写法:面试中看到很多人写作 mid = (high-low)/2,这种写法肯定是错误的,只要low不是0,就会出错。

  • 边界更新

        中间值小于目标值时,low=mid+1;中间值大于目标值时,high=mid-1;

        错误写法:low=mid; high=mid; 不但有重复计算,而且会导致死循环(例 low==high时)

注:此处的二分查找也可以通过递归实现,递归实现代码更加简洁,不过递归算法递归过深会有堆栈溢出的风险,面试中面试官也更愿意看到非递归的实现。

2. 二分查找的缺点

        看过了最基本的二分查找实现之后,我们可以发现二分查找有以下局限性:

  • 依赖数组实现,需要使用数组连续存储数据
  • 针对的是有序数据,必须是有序的数才能使用
  • 数据量太大太小都不适合,数据太大内存没有足够连续内存,数据太小体现不出性能优势

在实际应用中,很难保证数据不会有重复,而且我们可能需要查找满足条件的第一个或最后一个元素,下面看看二分查找的一些变体:

3. 二分查找的下界 查找第一个等于目标值的元素

int binarySearch(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) {
      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;
}
二分查找及其变种实现

        这个有序数组中有重复的元素,需要查找出第一个等于目标值的元素。相对第一个算法仅修改了算法退出条件(11-14行),当中间元素值等于目标数时:

  • 如果为数组第一个元素,或者mid左侧的数不为目标数时则返回mid
  • 否则 high=mid-1, 继续向左侧查找

4. 二分查找的上界 查找最后一个等于目标值的元素

int binarySearch(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) {
      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;
}
二分查找及其变种实现

这个有序数组中有重复的元素,需要查找出最后一个等于目标值的元素。还是只用修改算法退出条件(11-14行),当中间元素值等于目标数时:

  • 如果为数组最后一个元素,或者mid右侧的数不为目标数时则返回mid
  • 否则 low=mid+1, 继续向右侧查找

5. 查找第一个大于等于目标值的元素

int binarySearch(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) {
      if ((mid == 0) || (a[mid - 1] < value)) 
        return mid;
      else 
        high = mid -1;
    } else{
      low = mid + 1;
    }
  }
  return -1;
}
二分查找及其变种实现

这个有序数组中有重复的元素,需要查找出第一个等于目标值的元素。相对于查找第一个等于元素的算法,修改算法结束条件,当中间元素值大于等于目标数时:

  • 如果为数组第一个元素,或者mid左侧的数小于目标数时则返回mid
  • 否则 high=mid-1, 继续向左侧查找

6. 查找最后一个小于等于目标值的元素

int binarySearch(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) {
      if ((mid == n-1) || (a[mid + 1] > value)) 
        return mid;
      else 
        low = mid + 1;
    } else{
      high = mid - 1;
    }
  }
  return -1;
}
二分查找及其变种实现

        这个有序数组中有重复的元素,需要查找出第一个等于目标值的元素。相对于查找最后一个等于元素的算法,修改算法结束条件,当中间元素值小于等于目标数时:

  • 如果为数组最后一个元素,或者mid右侧的数大于目标数时则返回mid
  • 否则 low=mid+1, 继续向右侧查找

7. 二分查找的优势

       通过学习以上二分查找的变体,我们发现二分查找很适合区间查找,而且时间复杂度都为O(logn)。实际上在工程上一般的查找场景都是使用二叉搜索树(例如红黑树)或者哈希表来实现的,二分查找的优势在于对有序数组的区间查找,二叉搜索树和哈希表区间查找不方便。

       此外我们知道二分查找依赖于数组实现,链表要实现二分查找,可以使用跳跃表(Skip List)来实现,redis中正是使用跳表实现了键值的高效区间查找。

?

二分查找及其变种实现

上一篇:使用Nginx和路由将端口转发到Node.js应用程序


下一篇:linux – 所有接口的组播路由