【二分算法】——8个题目让你找到二分算法的感觉势如破竹

文章目录

1.二分查找
2.在排序数组中查找元素的第一个和最后一个位置
3.x的平方根
4.搜索插入位置
5.山脉数组的峰顶索引
6.寻找峰值
7.寻找旋转排序数组中的最小值
8.JZ53(2)

1.二分查找

https://leetcode.cn/problems/binary-search/
在这里插入图片描述

思路: 标准的二分查找。给定一个有序数组和目标值，每次选择数组的中间元素与目标值比较。如果中间元素等于目标值，则返回该索引；若中间元素小于目标值，则在右侧继续搜索；若中间元素大于目标值，则在左侧继续搜索。时间复杂度为O(log n)。

步骤: 初始化: 设置 left 和 right 分别为数组的开头和结尾。
二分查找: 计算中点 mid。
如果 nums[mid]等于目标值，返回 mid。
如果 nums[mid] 小于目标值，更新 left = mid + 1。
如果 nums[mid]大于目标值，更新 right = mid - 1。终止条件: 如果没有找到，返回 -1。

class Solution 
{
public:
    int search(vector<int>& nums, int target) 
    {
        int n = nums.size(); // 获取数组的大小
        // 定义左右边界，left 是左边界，right 是右边界
        for(int left = 0,right = n - 1;left <= right;) 
        {
            // 计算中间索引 mid，避免溢出的安全写法可以使用：mid = left + (right - left) / 2;
            int mid = (left + right) / 2;
            // 如果中间值小于目标值，说明目标值在右半部分，移动左边界到 mid + 1
            if(nums[mid] < target) left = mid + 1;
            // 如果中间值大于目标值，说明目标值在左半部分，移动右边界到 mid - 1
            if(nums[mid] > target) right = mid - 1;
            // 如果中间值等于目标值，返回当前中间值的索引
            if(nums[mid] == target) return mid;
        }
        // 如果没有找到目标值，返回 -1
        return -1;
    }
};

2.在排序数组中查找元素的第一个和最后一个位置

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
在这里插入图片描述
思路: 这是经典的“查找范围”问题，可以用两次二分查找解决。第一次找第一个出现位置，第二次找最后一个出现位置。时间复杂度为O(log n)，适合处理排序数组。

步骤:
查找第一个位置: 使用二分查找，找到目标值的第一个位置。
每次判断 nums[mid] 是否大于等于target，是则向左移动，否则向右移动。
查找最后一个位置: 使用二分查找，找到目标值的最后一个位置。
每次判断 nums[mid]是否小于等于 target，是则向右移动，否则向左移动。
返回结果: 如果找到两个位置，返回它们的范围，否则返回 [-1, -1]。

class Solution 
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        // 如果数组为空，直接返回 {-1, -1}
        if(nums.size() == 0) return {-1, -1};
        
        // 获取数组的大小
        int n = nums.size();
        
        // 初始化左右边界
        int left = 0, right = n - 1;
        
        // 查找左端点，目标是找到 target 第一次出现的位置
        while(left < right)
        {
            // 计算中间索引，防止溢出的安全写法
            int mid = left + (right - left) / 2;
            
            // 如果中间值小于目标值，说明目标值在右侧，将 left 移到 mid + 1
            if(nums[mid] < target) left = mid + 1;
            
            // 如果中间值大于等于目标值，右边界移动到 mid，继续查找
            if(nums[mid] >= target) right = mid;
        }
        
        // 如果左边界的值不等于 target，说明数组中没有该值，返回 {-1, -1}
        if(nums[left] != target) return {-1, -1};
        
        // 记录找到的目标值的起始位置
        int begin = left;
        
        // 查找右端点，目标是找到 target 最后一次出现的位置
        right = n - 1;  // 重新初始化右边界
        
        // 使用二分查找找右边界
        while(left < right)
        {
            // 计算中间索引，为了确保 mid 偏向右侧，加 1
            int mid = left + (right - left + 1) / 2;
            
            // 如果中间值小于等于目标值，说明右边界可能在右侧，将 left 移动到 mid
            if(nums[mid] <= target) left = mid;
            
            // 如果中间值大于目标值，说明右边界在左侧，将 right 移到 mid - 1
            if(nums[mid] > target) right = mid - 1;
        }
        
        // 返回目标值的起始和结束位置
        return {begin, right};
    }
};

3.x的平方根

https://leetcode.cn/problems/sqrtx/
在这里插入图片描述
思路: 使用二分查找法求x的平方根。定义初始范围为0,x，每次取中间值m，计算m²与x的比较。如果m²小于x，则移动左边界；如果m²大于x，则移动右边界。直至找到平方根或其整数部分。

步骤:
初始化: 设置 left 为 0，right 为 x。
二分查找: 计算中点 mid。
如果 mid * mid 小于x，说明平方根在右侧，更新 left = mid + 1。
如果 mid * mid 大于 x，说明平方根在左侧，更新 right =mid - 1。
终止条件: 当 left 和 right 相遇时，取较小值作为结果的整数部分。

class Solution 
{
public:
    int mySqrt(int x) 
    {
        // 定义二分查找的左右边界
        int left = 1, right = x;
        
        // 如果 x 小于 1，直接返回 0
        if(x < 1) return 0;
        
        // 开始二分查找
        while(left < right)
        {
            // 计算中间值，为了避免溢出，使用 left + (right - left + 1) / 2
            long long mid = left + (right - left + 1) / 2;
            
            // 如果 mid 的平方小于等于 x，说明 mid 可能是答案，或者答案在右侧，将 left 移动到 mid
            if(mid * mid <= x) left = mid;
            // 如果 mid 的平方大于 x，说明 mid 太大，答案在左侧，将 right 移动到 mid - 1
            else if(mid * mid > x) right = mid - 1;
        }
        
        // 返回找到的平方根的整数部分
        return left;
    }
};

4.搜索插入位置

https://leetcode.cn/problems/search-insert-position/description/
在这里插入图片描述
思路: 给定一个有序数组和目标值，要求返回目标值在数组中的插入位置。如果数组中存在目标值，返回其索引；若不存在，返回其应该插入的位置。使用二分查找，找到第一个大于或等于目标值的位置。

步骤:
初始化: 使用 left 和 right 指针。
二分查找: 计算中点 mid。
如果 nums[mid] 大于或等于目标值target，则将 right 更新为 mid - 1。
否则，将 left 更新为 mid + 1。
终止条件: 当 left 和right 相遇时，left 即为目标值要插入的位置。

class Solution 
{
public:
    int search(vector<int>& nums, int target) 
    {
        int n = nums.size(); // 获取数组的大小
        // 定义左右边界，left 是左边界，right 是右边界
        for(int left = 0,right = n - 1;left <= right;) 
        {
            // 计算中间索引 mid，避免溢出的安全写法可以使用：mid = left + (right - left) / 2;
            int mid = (left + right) / 2;
            // 如果中间值小于目标值，说明目标值在右半部分，移动左边界到 mid + 1
            if(nums[mid] < target) left = mid + 1;
            // 如果中间值大于目标值，说明目标值在左半部分，移动右边界到 mid - 1
            if(nums[mid] > target) right = mid - 1;
            // 如果中间值等于目标值，返回当前中间值的索引
            if(nums[mid] == target) return mid;
        }
        // 如果没有找到目标值，返回 -1
        return -1;
    }
};

5.山脉数组的峰顶索引

https://leetcode.cn/problems/peak-index-in-a-mountain-array/
在这里插入图片描述

思路: 山脉数组是先递增后递减的数组，因此其峰顶就是数组中最大值的位置。可以使用二分查找，类似“寻找峰值”的思路，找到这个峰顶索引。

步骤:
初始化: 使用 left 和 right 指针，分别指向数组的开头和结尾。
二分查找: 计算中点 mid。如果 nums[mid]大于 nums[mid + 1]，峰顶在左侧，更新 right = mid。
如果 nums[mid] 小于 nums[mid + 1]，峰顶在右侧，更新 left = mid + 1。
终止条件: 当 left 和 right 相遇时，left 即为峰顶的索引。

class Solution 
{
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        // 获取数组大小
        int n = arr.size();
        
        // 定义左右边界。由于数组两端不能是峰值，山峰一定在1到n-2之间
        int left = 1, right = n - 2;
        
        // 当左边界小于右边界时，继续查找
        while(left < right)
        {
            // 计算中间位置，使用 left + (right - left + 1) / 2 可以避免溢出
            int mid = left + (right - left + 1) / 2;
            
            // 如果中间元素比左侧的前一个元素小，说明山峰在左边，右边界移动到 mid - 1
            if(arr[mid] < arr[mid - 1]) right = mid - 1;
            // 否则，山峰在右侧或当前位置，左边界移动到 mid
            else left = mid;
        }
        
        // 循环结束时，left 和 right 会指向同一个位置，这就是峰值的索引
        return left;
    }
};

6.寻找峰值

https://leetcode.cn/problems/find-peak-element/description/
在这里插入图片描述
思路: 峰值定义为该元素比相邻元素大。可以使用二分查找的变种。每次选择中点，如果中点比其右侧元素小，则峰值在右侧；如果中点比其右侧元素大，则峰值在左侧。这样逐步缩小搜索范围，直至找到峰值。

步骤:
初始化: 定义 left 和 right 指针。
二分查找: 每次计算中点 mid。如果 nums[mid] 大于 nums[mid + 1]，说明峰值在左侧或就是 mid，更新 right = mid。
如果 nums[mid] 小于 nums[mid + 1]，说明峰值在右侧，更新 left = mid + 1。
终止条件: 当 left 和 right 相遇时，left 即为峰值所在的位置。

class Solution 
{
public:
    int findPeakElement(vector<int>& nums) 
    {
        // 初始化左右边界
        int left = 0, right = nums.size() - 1;
        
        // 二分查找
        while(left < right)
        {
            // 计算中间索引，避免溢出
            int mid = left + (right - left) / 2;
            
            // 如果中间值大于它右边的元素，说明峰值在左侧或当前元素是峰值，将右边界移到 mid
            if(nums[mid] > nums[mid + 1]) right = mid;
            // 如果中间值小于它右边的元素，说明峰值在右侧，将左边界移到 mid + 1
            else left = mid + 1;
        }
        
        // 返回最终找到的峰值索引
        return left;
    }
};

7.寻找旋转排序数组中的最小值

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
在这里插入图片描述
思路: 旋转排序数组的特点是其包含两个有序的子数组（前一段大于后一段）。最小值通常出现在这两个有序子数组的交界处。可以使用二分查找，比较中点和右端点的值，若中点大于右端点，最小值在右侧；若中点小于右端点，最小值在左侧。

步骤:
初始化: 定义 left 和 right 指针。
二分查找: 每次计算中点 mid。
如果 nums[mid] 大于 nums[mid + 1]，说明峰值在左侧或就是 mid，更新 right = mid。
如果 nums[mid] 小于 nums[mid +1]，说明峰值在右侧，更新 left = mid + 1。
终止条件: 当 left 和 right 相遇时，left 即为峰值所在的位置。

class Solution 
{
public:
    int findMin(vector<int>& nums) 
    {
        int n = nums.size();   // 获取数组大小
        int left = 0, right = n - 1;   // 初始化左右边界
        
        // 二分查找
        while(left < right) 
        {
            int mid = left + (right - left) / 2;   // 计算中间索引，避免溢出
            
            // 如果中间值大于最右侧值，说明最小值在右侧，更新 left
            if(nums[mid] > nums[right]) left = mid + 1;
            
            // 否则，最小值在左侧或当前 mid 处
            else right = mid;
        }
        
        // 最小值在 left 处
        return nums[left];
    }
};

8.JZ53(2)

《剑指offer面试题53II》
题目类型: 0〜n-1 中缺失的数字（面试题53 - II）
因为这题作者在leetcode中未找到这题原题，不过有一道类似题目
（这题在leetcode消失的原因是剑指offer在leetcode上下架了）
https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/
在这里插入图片描述

思路: 因为数组是排好序的，可以使用二分查找分别找到目标数字的第一个出现位置和最后一个出现位置。然后计算出最后一次出现位置与第一次出现位置的差值，得到出现的次数。

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

        // 如果最终找到的位置的索引值等于该位置的记录值，则返回 left + 1，否则返回 left
        return left == records[left] ? left + 1 : left;
    }
};