当前位置:   article > 正文

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

折半查找平均比较次数公式

二分查找法简介

  二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
  首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
  算法要求:1.必须采用顺序存储结构。2.必须按关键字大小有序排列。
  比较次数的计算公式:a<log2n<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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/624490
推荐阅读
相关标签
  

闽ICP备14008679号