【数据结构与算法】二分查找

风中的云彩

发布于 2025-05-13 08:31:34

1910

技巧

基础模板

1. 定义两个指针来表示两边端点，left--->左端点，right--->右端点。 2. 二分查找的区间为[left,right]，闭区间内任意一点都为未知数。 3. 循环的判断结束条件为left<=right，时间复杂度为O(logN)。 4. 为了防止整数溢出，可以使用mid=left+(right-left)/2或mid=left+(right-left+1)/2。 5. 当数组中元素的个数为偶数时，left+(right-left)/2求出的是偏左的中点，left+(right-left+1)/2求出的是偏右的中点；当数组中元素的个数为奇数时，两者都是正好找到中点。 6. 适用二分查找的情况：数组具备二段性，而非单调性。所以二分查找的重点是去发现数组的二段性。

while(left<=right)
{
    int mid=left+(right-left)/2;
    if(nums[mid]>target)
        right=mid-1;
    else if(nums[mid]<target)
        left=mid+1;
    else
         return mid;
}

左查找模板

1. 定义两个指针来表示两边端点，left--->左端点，right--->右端点。 2. 二分查找的区间为[left,right]，闭区间内任意一点都为未知数。 3. 循环的判断结束条件为left<right，不能取等号(会陷入死循环)，时间复杂度为O(logN)。 4. 为了防止整数溢出，只能使用mid=left+(right-left)/2，不能使用mid=left+(right-left+1)/2(会陷入死循环)。 5. 查找左端点，right必须承担等号；查找右端点，left必须承担等号。 6. 若两种情况均未触发+1或-1操作，算法将在left==right-1时，进入无限循环状态。

while(left<right)
{
    int mid=left+(right-left)/2;
    if(nums[mid]<target)
        left=mid+1;
    else
        right=mid;
}
//跳出循环时:left==right
if(nums[left]==target)
    return left;

右查找模板

1. 定义两个指针来表示两边端点，left--->左端点，right--->右端点。 2. 二分查找的区间为[left,right]，闭区间内任意一点都为未知数。 3. 循环的判断结束条件为left<right，不能取等号(会陷入死循环)，时间复杂度为O(logN)。 4. 为了防止整数溢出，只能使用mid=left+(right-left+1)/2，不能使用mid=left+(right-left)/2(会陷入死循环)。 5. 查找左端点，right必须承担等号；查找右端点，left必须承担等号。 6. 若两种情况均未触发+1或-1操作，算法将在left==right-1时，进入无限循环状态。

while(left<right)
{
    int mid=left+(right-left+1)/2;
    if(nums[mid]=<target)
        left=mid;
    else
        right=mid-1;
}
//跳出循环时:left==right
if(nums[right]==target)
    return right;

例题

1. leetcode-704题： 704. 二分查找 - 力扣（LeetCode）

https://leetcode.cn/problems/binary-search/

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

2. leetcode-34题： 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/628784409/

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        vector<int> v;
        int left=0,right=nums.size()-1;
        if(nums.size()==0)
            return {-1,-1};

        while(left<right)//找左端点
        {
            int mid=left+(right-left)/2;
            if(nums[mid]<target)
                left=mid+1;
            else
                right=mid;
        }
        if(nums[left]==target)
            v.push_back(left);
        else
            return {-1,-1};

        left=0,right=nums.size()-1;
        while(left<right)//找右端点
        {
            int mid=left+(right-left+1)/2;
            if(nums[mid]>target)
                right=mid-1;
            else
                left=mid;
        }
        if(nums[right]==target)
            v.push_back(right);
        else
            return {-1,-1};
        
        return v;
    }
};

3. leetcode-69题： 69. x 的平方根 - 力扣（LeetCode）

https://leetcode.cn/problems/sqrtx/

class Solution {
public:
    int mySqrt(int x) 
    {
        int i=0;
        while(1)
        {
            if((long long)i*i<=(long long)x&&(long long)(i+1)*(i+1)>(long long)x)
                return i;
            i++;
        }
    }
};

class Solution {
public:
    int mySqrt(int x) 
    {
        if(x<1)
            return 0;
        long long left=0,right=x;
        while(left<right)
        {
            long long mid=left+(right-left+1)/2;
            if(mid*mid<=x)
                left=mid;
            else
                right=mid-1;
        }
        return left;
    }
};

4. leetcode-35题： 35. 搜索插入位置 - 力扣（LeetCode）

https://leetcode.cn/problems/search-insert-position/

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

5. leetcode-852题： 852. 山脉数组的峰顶索引 - 力扣（LeetCode）

https://leetcode.cn/problems/peak-index-in-a-mountain-array/

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        int left=0,right=arr.size()-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(arr[mid]>arr[mid+1])
                right=mid;
            else
                left=mid;
            if(left==right-1)
                break;
        }
        if(arr[left]<arr[right])
            return right;
        else
            return left;
    }
};

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        int left=0,right=arr.size()-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(arr[mid]>arr[mid+1])
                right=mid;
            else
                left=mid+1;
        }
        return left;
    }
};

6. leetcode-162题： 162. 寻找峰值 - 力扣（LeetCode）

https://leetcode.cn/problems/find-peak-element/submissions/629136551/

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

7. leetcode-162题： 153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/submissions/629221865/

class Solution {
public:
    int findMin(vector<int>& nums) 
    {
        if(nums.size()==1)
            return nums[0];
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]>nums[mid+1])
            {
                right=mid+1;
                break;
            }
            else if (nums[mid]>nums[0])
                left=mid+1;
            else
                right=mid;
        }
        int ret=min(nums[right],nums[0]);
        return ret;
    }
};

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

8. leetcode-173题： LCR 173. 点名 - 力扣（LeetCode）

https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/

class Solution {
public:
    int takeAttendance(vector<int>& records) 
    {
        int left=0,right=records.size()-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(records[mid]==mid)
                left=mid+1;
            else
                right=mid;
        }
        if(records[right]==right)
            return right+1;
        else
            return right;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-05-12，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构与算法