【算法积累】二分查找法_折半查找平均比较次数公式

二分查找法简介

  二分查找也称折半查找(Binary Search)，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
  首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
  算法要求：1.必须采用顺序存储结构。2.必须按关键字大小有序排列。
  比较次数的计算公式：a<log₂n<b，其中a,b,n均为正整数。即当顺序表有n个关键字时：查找失败至少比较a次关键字，查找成功最多比较关键字次数是b。

二分查找法模板

  以Java为例：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                // 相关逻辑
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 相关返回值
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

  或者：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length;
        while(left < right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                // 相关逻辑
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid; // 注意
            }
        }
        // 相关返回值
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

注：上述代码参考LeetCode用户灵魂画师牧码的题解画解算法：35.搜索插入位置。链接：link

实例

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
注：该题目出自LeetCode题库35.搜索插入位置。

  这道题最容易想到的方法是遍历法。代码实现如下：

// 语言：C
// 执行用时：8ms
// 内存消耗：7.2MB
int searchInsert(int* nums, int numsSize, int target){
    int i;
    for (i = 0; i < numsSize; i++)
    {
        if (nums[i] >= target)
            return i;
    }
    return i;
}
1
2
3
4
5
6
7
8
9
10
11
12

  应用二分查找法，代码如下：

// 语言：Java
// 执行用时：0ms（具体原因未知，可能是因为提交的时候网络卡顿）
// 内存消耗：39.2MB
class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] > target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 语言：C
// 执行用时：8ms
// 内存消耗：7.1MB
int searchInsert(int* nums, int numsSize, int target){
    int l, r;
    l = 0;
    r = numsSize - 1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (nums[m] == target)
            return m;
        else if (nums[m] > target)
            r = m - 1;
        else
            l = m + 1;
    }
    return l;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

  当然，我们还可以使用Python无脑解决这个问题：

"""
语言：Python3
执行用时：44ms
内存消耗：13.5MB
"""
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target in nums:
            return nums.index(target)
        else:
            nums.append(target)
            nums = sorted(nums)
            return nums.index(target)
1
2
3
4
5
6
7
8
9
10
11
12
13

  在逛LeetCode评论区的时候，还看到了一位大神李达西的Python“一行流”解法：

"""
语言：Python3
执行用时：据该用户的说法是50ms
内存消耗：未知
"""
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return len([i for i in nums if i < target])
1
2
3
4
5
6
7
8