目錄
二分查找
在排序數組中查找元素的第一個和最后一個位置
搜索插入位置
x的平方根
山峰數組的峰頂索引
尋找峰值
搜索旋轉排序數組中的最?值
點名
?二分查找模板分為三種：1、樸素的二分模板? ?2、查找左邊界的二分模板? 3、查找右邊界的二分模板（注意：不是數組有序才使用二分查找，只要存在二段性（一個條件把數組分為兩段）都可以使用二分查找）
二分查找
?代碼如下：
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)right = mid - 1;else if (nums[mid] < target)left = mid + 1;elsereturn mid;}return -1;}
};在排序數組中查找元素的第一個和最后一個位置
這道題可以引出另外兩個重要的二分查找模板：?查找左邊界的二分模板? ?查找右邊界的二分模板
?以上是兩個模板的內容，判斷條件根據題目內容修改，以題目示例1為例，下面給出具體解釋為什么這樣做可行：
?代碼如下：
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {// 處理為空if (nums.size() == 0)return { -1,-1 };// 找左端點int left_end_point = -1, right_end_point = -1;int left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1;elseright = mid;}// 判斷是否有結果if(nums[left]==target)left_end_point = left;// 找右端點 // left可以從左端點開始left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right - left + 1) / 2;if (nums[mid] > target)right = mid - 1;elseleft = mid;}if(nums[right] == target)right_end_point = right;if(right_end_point != -1)return { left_end_point,right_end_point };elsereturn { -1,-1 };}
};搜索插入位置
根據 二段性，可以把數組分為小于t和大于等于t兩部分，目標索引就是在大于等于的左邊界上。
注意示例3的邊界情況，代碼如下：
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size();while (left < right){int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1;elseright = mid;}// 數組中所有元素小于targetif (nums[left] < target)return left + 1;return right;}
};x的平方根
本題依舊是一個二分查找的算法思想，left為1，right為x本身，根據二段性，將x分為小于等于sqrt（x）的和大于sqrt（x）的，注意小于1的小數和INT_MAX這兩個特殊情況，?INT_MAX平方后數據太大，要用long long類型來存儲。代碼如下：
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)right = mid - 1;elseleft = mid;}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])right = mid - 1;elseleft = mid;}return 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;if (nums[mid] < nums[mid + 1])left = mid + 1;elseright = mid;}return left;}
};搜索旋轉排序數組中的最?值
class Solution {
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1, target = nums[right];while (left < right){int mid = left + (right - left) / 2;if (nums[mid] > target)left = mid + 1;elseright = 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;elseright = mid;}// 特殊情況0 1 2 3 缺少4return records[left] == left ? left + 1 : left;}
};
