算法剖析：二分查找

---

前言

二分查找是一种高效的查找算法，适用于有序数组。通过不断将查找范围缩小为一半，它在 O(log n) 时间内定位目标元素，大幅提高查找效率。

二分查找适用于可将数据划分为两块的情况，不一定非要排序。

---

二分查找模板

朴素模板

---

左右查找模板

---

一、二分查找

二分查找

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

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

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

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0) return {-1, -1};int begin = 0;int left = 0, right = nums.size() - 1;//1. 查找左边界while (left < right){int mid = left + (right - left) / 2;if (nums[mid] < target) left = mid + 1;else right = mid;}//判断值是否是我们要的targetbegin = left;if (nums[begin] != target){return {-1, -1};}//小优化，查右边left不用更新，right要更新right = nums.size() - 1;while (left < right){int mid = left + (right - left + 1) / 2;if (nums[mid] <= target) left = mid;else right = mid - 1; }return {begin, right};}
};

---

三、搜索插入位置

搜索插入位置

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

---

四、x 的平方根

x 的平方根

class Solution {
public:int mySqrt(int x) {if(x < 1) return 0;int left = 1, 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;}
};

---

五、山脉数组的峰顶索引

山脉数组的峰顶索引

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

---

六、寻找峰值

寻找峰值

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

---

七、寻找旋转排序数组中的最小值

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

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

---

八、 点名

点名

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; }return left == records[left] ? left + 1 : left;}
};

---

总结

到这里我们二分查找就结束啦，谢谢大家😘😘😘😘(～￣▽￣)～