欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【算法积累】二分查找法

程序员文章站 2023-12-22 13:49:58
...

二分查找法简介

  二分查找也称折半查找(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;
    }
}

  或者:

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;
    }
}

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

实例

题目:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
注:该题目出自LeedCode题库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;
}

  应用二分查找法,代码如下:

// 语言: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;
    }
}
// 语言: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;
}

  当然,我们还可以使用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)

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

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

上一篇:

下一篇: