二分搜索算法解题步骤！

二分搜索（折半搜索）是一种在有序数组中查找某一特定元素的搜索算法。

  • 时间复杂度是 O(lgn)，非常高效。

基本特点

要求待查找的数组或者区间是排好序的。

如果对数组进行动态的删除和插入操作并完成查找，平均复杂度会变为 O(n)。

当输入的数组或者区间是排好序的，同时又不会经常变动。

  • 而要求从里面找出一个满足条件的元素的时候，二分搜索就是最好的选择。

解题思路

二分搜索解题思路如下：

从已经排好序的数组或区间中取出中间位置的元素，判断该元素是否满足要搜索的条件。

  • 如果满足，停止搜索，程序结束。

如果正中间的元素不满足条件，则从它两边的区域进行搜索。

由于数组是排好序的，可以利用排除法，确定接下来应该从这两个区间中的哪一个去搜索。

通过判断，如果发现真正要找的元素在左半区间的话，就继续在左半区间里进行二分搜索。

反之，就在右半区间里进行二分搜索。

解题框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
     //计算 mid 时需要技巧防止溢出，建议写成: mid = left + (right - left) / 2
        int mid = (right + left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

递归解法:

从排好序的数组 {1, 3, 4, 6, 7, 8, 10, 13, 14} 查找数字 7 是否在里面，如果在，返回它的下标，否则返回 -1。

  • 在计算 middle 下标的时候，不能用 (low + hight) / 2，可能会导致溢出。

  • 在取左半边以及右半边的区间时，左半边是 [low, middle - 1]，右半边是[middle + 1, high]，这是两个闭区间。

  • 因为已经确定了 middle 那个点不是要找的，就没有必要再把它加入到左、右半边了。

  • 对于一个长度为奇数的数组，例如：{1, 2, 3, 4, 5}，按照 low + (high - low) / 2 来计算。

  • middle 就是正中间的那个位置，对于一个长度为偶数的数组，例如 {1, 2, 3, 4}，middle 就是正中间靠左边的一个位置。

最后的时间复杂度是 O(logn)。

递归写法的代码模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 二分搜索函数的定义里，除了要指定数组 nums 和目标查找数 target 之外，还要指定查找区间的起点和终点位置，分别用 low 和 high 去表示。
int binarySearch(int[] nums, int target, int low, int high) {
        // 为了避免无限循环，先判断，如果起点位置大于终点位置，表明这是一个非法的区间，已经尝试了所有的搜索区间还是没能找到结果，返回 -1。 

 if (low > high) {
        return -1;
    }
    // 取正中间那个数的下标 middle。
    int middle = low + (high - low) / 2;
    
    // 判断一下正中间的那个数是不是要找的目标数 target，是，就返回下标 middle。    
    if (nums[middle] == target) {
        return middle;
    }
    
    // 如果发现目标数在左边，就递归地从左半边进行二分搜索。
    if (target < nums[middle]) {
        return binarySearch(nums, target, low, middle - 1);
      } else {
        return binarySearch(nums, target, middle + 1, high);
    }//否则从右半边递归地进行二分搜索。
}

非递归解法：

非递归写法的代码模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int binarySearch(int[] nums, int target, int low, int high) {
    // 在 while 循环里，判断搜索的区间范围是否有效
    while (low <= high) {
        // 计算正中间的数的下标
        int middle = low + (high - low) / 2;
    
     // 判断正中间的那个数是不是要找的目标数 target。如果是，就返回下标 middle
     if (nums[middle] == target) {
         return middle;
     }
    
     // 如果发现目标数在左边，调整搜索区间的终点为 middle - 1；否则，调整搜索区间的起点为 middle + 1
     if (target < nums[middle]) {
         high = middle - 1;
       } else {
         low = middle + 1;
       }
     }

     // 如果超出了搜索区间，表明无法找到目标数，返回 -1  
     return -1;
}