算法每日双题精讲 —— 二分查找（二分查找，在排序数组中查找元素的第一个和最后一个位置）

🌟快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。 🌟

别再犹豫了！快来订阅我们的算法每日双题精讲专栏，一起踏上算法学习的精彩之旅吧！💪

在算法的浩瀚星空中✨，二分查找算法宛如一颗璀璨的明星🌟，闪耀着简洁与高效的光芒。今天，就让我们一同聚焦于 “二分查找” 以及 “在排序数组中查找元素的第一个和最后一个位置” 这两道经典题目，深度挖掘二分查找算法的奥秘与应用技巧🤓。

不要跳过每一个二分查找算法文章哦，难度逐渐提升！

二分查找简介

一、二分查找

📖题目描述

🧠讲解算法原理

💻代码实现（以 C++ 为例）

复杂度分析

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

📖题目描述

🧠讲解算法原理

💻代码实现（以 C++ 为例）

复杂度分析

二分查找简介

特点：最恶心，细节最多，最容易写出死循环，但是掌握就是最简单的算法

二分查找有三个模板：

朴素的二分模板——easy，局限
查找左边界的二分模板——万能，细节多
查找右边界的二分模板

一、二分查找

题目链接👉【力扣】

📖题目描述

🧠讲解算法原理

二分查找的核心思想犹如在一本有序的字典中查找单词📕，每次都能通过中间元素将搜索区间大致缩小一半。"二段性"
首先，我们设定两个指针，left 指向数组的起始位置，right 指向数组的末尾位置。然后，在循环中计算中间索引 mid = left + (right - left) / 2（这种计算方式可有效避免整数溢出）。接下来，比较 nums[mid] 与 target 的大小关系：

若 nums[mid] == target，则幸运地找到了目标值，直接返回 mid 😀。
若 nums[mid] < target，这表明目标值在中间元素的右侧，于是将 left 更新为 mid + 1，继续在右侧区间查找。
若 nums[mid] > target，意味着目标值在中间元素的左侧，此时将 right 更新为 mid - 1，继续在左侧区间探索。
循环持续进行，直到 left 大于 right，表示整个数组都已搜索完毕但未找到目标值，此时返回 -1。

💻代码实现（以 C++ 为例）

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 (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
};

复杂度分析

时间复杂度：由于每次循环都能将搜索区间缩小一半，最多需要进行 $log_2 n$ 次比较，所以时间复杂度为 $O(log n)$ ，其中 n 为数组的长度。这使得二分查找在处理大规模有序数据时表现极为出色，相比暴力遍历数组的 $O(n)$ 时间复杂度，效率有了质的飞跃🚀！
空间复杂度：整个查找过程只需要使用几个额外的指针变量来记录索引和中间位置，无需额外的数据结构来存储数据，所以空间复杂度为 $O(1)$ ，具有极高的空间效率👍！

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

题目链接👉【力扣】

📖题目描述

🧠讲解算法原理

首先，借二分查找思想找到目标值任一位置😃。找首位置时，从该位置向左搜，遇到首个不等元素，其下一位即目标首位置🧐；找尾位置同理，从找到处向右搜，遇到首个不等元素，其前一位即目标尾位置。

为避免代码重复，编写辅助函数实现二分查找核心逻辑，主函数调用它分别找目标值首尾位置😎。

💻代码实现（以 C++ 为例）

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        // 如果数组为空，直接返回{-1, -1}，表示未找到目标值的起始和结束位置
        if(nums.size()==0) return {-1,-1}; 

        vector<int> x;
        int left = 0, right = nums.size() - 1;
        int mid = 0;

        // 查找目标值的左边界
        while(left < right) 
        {
            // 计算中间位置，防止(left + right)溢出
            mid = left+(right - left)/2; 
            if(nums[mid] >= target) 
            {
                // 如果中间值大于等于目标值，说明目标值的左边界可能在左半部分（包括mid）
                right = mid; 
            }
            if(nums[mid] < target) 
            {
                // 如果中间值小于目标值，说明目标值的左边界在右半部分
                left = mid + 1; 
            }
        }
        // 检查找到的left位置是否为目标值
        if(nums[left] == target)    
            x.push_back(left);
        else
            x.push_back(-1);

        // 重置left和right，准备查找目标值的右边界
        left = 0; right = nums.size() - 1; 
        // 查找目标值的右边界
        while(left < right) 
        {
            // 这里加1是为了保证在left和right相差1时，mid能取到right，避免死循环
            mid = left+(right - left + 1)/2; 
            if(nums[mid] > target) 
            {
                // 如果中间值大于目标值，说明目标值的右边界在左半部分
                right = mid - 1; 
            }
            if(nums[mid] <= target) 
            {
                // 如果中间值小于等于目标值，说明目标值的右边界可能在右半部分（包括mid）
                left = mid; 
            }
        }
        // 检查找到的left位置是否为目标值
        if(nums[left] == target)    
            x.push_back(left);
        else
            x.push_back(-1);

        return x;
    }
};