算法剖析：二分查找

文章目录

前言
二分查找模板
- 朴素模板
- 左右查找模板
一、二分查找
二、在排序数组中查找元素的第一个和最后一个位置
三、搜索插入位置
四、x 的平方根
五、山脉数组的峰顶索引
六、寻找峰值
七、寻找旋转排序数组中的最小值
八、点名
总结

前言

二分查找是一种高效的查找算法，适用于有序数组。通过不断将查找范围缩小为一半，它在 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;}
};