什么是二分查找？

了解二分查找是什么以及我们如何实现它。

导入

什么是二分查找？

了解二分查找是什么以及我们如何实现它。

二分查找（Binary Search，简称 BS）是最基本的搜索算法之一。在面试中，面试官常会提出需要使用二分查找才能实现最优解或唯一解的编程问题。这一点在现场面试中尤为重要，因为面试者通常只被要求解决两到四个问题。不幸的是，如果无法正确、无错误地使用二分查找，可能会成为面试中的一个警示信号。

二分查找也被称为半区间查找，这为我们提示了何时应使用它：如果我们能通过一个条件大致排除一半的搜索范围，那么我们就是在对目标进行二分查找。

处理边界情况！

候选人失败于二分查找面试题的最常见原因是未能妥善处理边界情况。

边界情况可能由多种原因造成，例如：目标值位于数组的第 0 个索引处、位于第 (n-1) 个索引处、循环陷入无限执行等。

幸运的是，只要每次坚持使用相同的策略，这些陷阱都可以避免。

接下来，我们将详细讲解这一通用方法。

一种通用的解决方案

1. 算法模式

这是一种独特的二分查找形式，它利用当前索引及其左右相邻索引。

以下是算法的核心要点，并逐一解释：

伪代码

1left = 0
2right = 数组长度
3
4while (left + 1 < right)
5  mid = (left + right) / 2
6
7  if (array[mid] == target)
8    返回 mid
9  else if (array[mid] < target)
10    在右半部分继续搜索
11  else
12    在左半部分继续搜索
13
14if (array[left] == target)
15  返回 left
16
17返回 -1

让我们逐行分析核心要点：

第 1 行：将 left 索引初始化为 0。
第 2 行：将 right 索引初始化为数组长度。因此，在检查 right 索引对应的元素时需格外小心。
第 4 行：当 left 和 right 之间没有剩余元素时，循环结束。因此，若数组仅有一个元素，循环将被跳过。
第 14 行：必须在循环外检查 left 索引处的元素，因为如果循环被跳过，该位置就可能是目标值。

2. 代码实现

以下是该方法的完整实现：

C++

1#include <iostream>
2#include <vector>
3using namespace std;
4
5int searchInsert(vector<int>& nums, int target) {
6  int left = 0;
7  int right = nums.size();
8  
9  while (left + 1 < right) {
10    int mid = (right + left) / 2;
11    
12    if (nums[mid] == target) {
13      return mid;
14    } else if (nums[mid] < target) {
15      left = mid;
16    } else {
17      right = mid;
18    }
19  }
20  
21  if (nums[left] == target) {
22    return left;
23  }
24  
25  return -1;
26}
27
28int main() {
29  vector<int> nums = {1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
30
31  cout << "37 的索引是 ---> " << searchInsert(nums, 37) << endl;
32  cout << "1 的索引是 ---> " << searchInsert(nums, 1) << endl;
33  cout << "59 的索引是 ---> " << searchInsert(nums, 59) << endl;
34  cout << "25 的索引是 ---> " << searchInsert(nums, 25) << endl;
35
36  return 0;
37}

Java

1class Solution {
2  int binarySearch(int[] nums, int target){
3    if (nums == null || nums.length == 0) {
4      return -1;
5    }
6
7    int left = 0;
8    int right = nums.length;
9    
10    while (left + 1 < right) {
11      int mid = (right + left) / 2;
12
13      if (nums[mid] == target) {
14        return mid;
15      } else if (nums[mid] < target) {
16        left = mid;
17      } else {
18        right = mid;
19      }
20    }
21    
22    if (nums[left] == target) {
23      return left;
24    }
25    
26    return -1;
27  }
28
29  public static void main(String[] args) {
30    Solution sol = new Solution();
31    int[] nums = new int[] {1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
32
33    System.out.println("37 的索引是 ---> " + sol.binarySearch(nums, 37));
34    System.out.println("1 的索引是 ---> " + sol.binarySearch(nums, 1));
35    System.out.println("59 的索引是 ---> " + sol.binarySearch(nums, 59));
36    System.out.println("25 的索引是 ---> " + sol.binarySearch(nums, 25));
37  }
38}

JavaScript

1const binarySearch = function(nums, target) {
2  if (!nums || nums.length === 0) {
3    return -1;
4  }
5
6  let left = 0;
7  let right = nums.length;
8  
9  while (left + 1 < right) {
10    let mid = Math.floor((right + left) / 2);
11
12    if (nums[mid] === target) {
13      return mid;
14    } else if (nums[mid] < target) {
15      left = mid;
16    } else {
17      right = mid;
18    }
19  }
20  
21  if (nums[left] === target) {
22    return left;
23  }
24  
25  return -1;
26}
27
28const nums = [1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59];
29
30console.log(`37 的索引是 ---> ${binarySearch(nums, 37)}`);
31console.log(`1 的索引是 ---> ${binarySearch(nums, 1)}`);
32console.log(`59 的索引是 ---> ${binarySearch(nums, 59)}`);
33console.log(`25 的索引是 ---> ${binarySearch(nums, 25)}`);

Python

1def binarySearch(nums, target):
2  if len(nums) == 0:
3    return -1
4
5  left = 0
6  right = len(nums)
7  
8  while left + 1 < right:
9    mid = (right + left) // 2
10
11    if nums[mid] == target:
12      return mid
13    elif nums[mid] < target:
14      left = mid
15    else:
16      right = mid
17  
18  if nums[left] == target:
19    return left
20  
21  return -1
22
23def main():
24  nums = [1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]
25
26  print("37 的索引是 ---> " + str(binarySearch(nums, 37)))
27  print("1 的索引是 ---> " + str(binarySearch(nums, 1)))
28  print("59 的索引是 ---> " + str(binarySearch(nums, 59)))
29  print("25 的索引是 ---> " + str(binarySearch(nums, 25)))
30
31main()

以下是一个通用情况下算法运行的可视化示例，目标值为 37：

下面我们验证该算法如何处理各种边界情况：

目标值是数组的第一个元素

目标值是数组的最后一个元素

目标值不存在于数组中

3. 详细说明

许多人在面对二分查找问题时，容易陷入具体问题细节的泥潭。但实际上，大多数二分查找题目都基于相同的核心思想。只要建立统一的解题基础，就能轻松应对各种变体。

我们的解题基础建立在五个简单而关键的原则之上：

left 索引始终指向数组的起始位置（即 0）。
right 索引始终指向数组长度。
while 循环的终止条件是 left + 1 >= right。
每次迭代中，将 left 或 right 更新为 mid。
在循环结束后，必须单独检查 left 索引处的元素。

下一节我们将分析该方法的时间与空间复杂度。

复杂度分析