二分法查找

Mustard 收录于 Data Structure

2022-03-01 约 300 字预计阅读 2 分钟 - 次阅读

前两天在LeetCode做题的时候, 做到了二分查找(Binary Search). 现在来做一下梳理.

地址: LeetCode-Binary Search

二分查找作为程序员的一个基本技能, 也是面试的时候有可能面试官会问到的一种算法. 可以达到O(log n)的时间复杂度.

一般来说, 当出现这几个条件的时候, 就应该用到二分查找:

待查找的数组是有序的或者是部分有序的
要求时间复杂度低于O(n), 或者直接说明时间复杂度是O(log n)

而且二分查找也有很多的变体. 在使用的时候, 要注意好查找条件, 判断条件以及左右边界的条件变更方式. 这三个地方没有注意好, 很容易就会出现死循环或是遗漏. 今天来梳理一下这几种:

标准的二分查找
二分查找左边界
二分查找右边界
二分查找的左右边界
二分查找极值点

标准的二分查找

上面这个题目就用标准的二分查找来实现, 我们先来看标准的二分查找的模板:

public int search(int[] array, int target) {
  int left = 0, right = array.length-1;
  // 1. 因为循环中包含了 left == right 的条件, 所以每次循环的时候, left或right都要有变化
  while (left <= right) {
    // 这句话其实等同于 (right+left)/2, 但是这样的写法可以避免溢出
    int mid = ((right - left) >> 1) + left;
    
    if (array[mid] == target) {
      return mid;
    } else if (array[mid] < target) {
      // 左边界更新
      left = mid + 1;
    } else {
      // 右边界更新
      right = mid - 1;
    }
  }
  // 未查找到目标值
  return -1;
}

二分查找左边界

使用这种变体的时候通常有这几种特性:

数组有序, 包含重复元素
数组部分有序, 包含重复元素
数组部分有序, 不包含重复元素

二分查找左边界①

这种分类包含了上面的1,3两种情况.

既然是查找左边界, 就要从右侧开始, 然后不断左移. 也就是说, 即使找到了array[mid] == target, 这个mid值也不见得就是要查找的左边界. 所以还是要继续收缩:

public int search(int[] array, int target) {
  int left = 0, right = array.length-1;
  
  while (left < right) {
    int mid = ((right - left) >> 1) + left;
				
    if (array[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return array[left] == target ? left : -1;
}

可以很明显的看出来和标准的有何不同:

查找条件变为了left < right

因为在最后left与right相邻的时候, mid和left处在同一位置. 所以下一步, left, mid, right都会在同一位置. 也就是说, 如果判断条件还是left <= right的话, 可能最后就会进入死循环.
右边界更新为right = mid

因为需要在查找到目标值之后继续向左移动.

二分查找左边界②

这种分类包含了上面的2情况, 也就是数组部分有序, 包含重复元素. 这种条件下, 右边界在向左移动的时候, 不能简单的令right = mid. 因为有重复的元素, 这样就可能会造成遗漏:

public int search(int[] array, int target) {
  int left = 0, right = array.length-1;
  
  while (left < right) {
    int mid = ((right - left) >> 1) + left;
    if (array[mid] < target) {
      left = mid + 1;
    } else if (array[mid] > target) {
      right = mid;
    } else {
      --right;
    }
  }
  return array[left] == target ? left : -1;
}