Giovanna

Appearance

Algorithm›代码随想录

二分查找（折半查找）

About 600 wordsAbout 2 min

基础算法

2024-07-07

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...

——Knuth

代码随想录 (programmercarl.com)

二分查找又称折半查找，是将序列中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将序列分成前、后两个子序列，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子序列，否则进一步查找后一子序列。重复以上过程，直到找到满足条件的记录，则查找成功，或直到子序列不存在为止，此时查找不成功。

三种应用场景：寻找一个数、寻找左侧边界、寻找右侧边界。

一、寻找一个数

704.二分查找

本题使用二分查找的前提条件：

  • 数组为有序数组
  • 数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

1. 左闭右闭

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        while(l<=r){
            int mid=l+(r-l)/2;             // 避免溢出
            if(nums[mid]>target) r=mid-1;
            else if(nums[mid]<target) l=mid+1;
            else return mid;
        }
        return -1;
    }
};

喜欢左闭右闭的写法。

2. 左闭右开

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0,r=nums.size();
        while(l<r){
            int mid=l+(r-l)/2;
            if(nums[mid]>target) r=mid;
            else if(nums[mid]<target) l=mid+1;
            else return mid;
        }
        return -1;
    }
};

二、寻找左侧边界

class Solution {
public:
	int left_bound(vector<int>& nums, int target) {
	    int l=0,r=nums.size();
	    while (l<r) {
	        int mid=l+(r-l)/2;
	        if(nums[mid]<target) l=mid+1;
	        else r=mid;
	    }
	    return l;
	}
}

等于时改变r。

三、寻找右侧边界

class Solution {
public:
	int right_bound(vector<int>& nums, int target) {
	    int l=0,r=nums.size();
	    while (l<r) {
	        int mid=l+(r-l)/2;
	        if(nums[mid]<=target) l=mid+1;
	        else r=mid;
	    }
	    return l-1;
	}
}

等于时改变l。

相关题目