一、二分查找
class Solution {
public:int search(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n-1;while(left <= right){int mid = (left+right)/2;if(nums[mid] > target) right = mid-1;else if(nums[mid] < target) left = 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};vector<int> ret;int n = nums.size();// 找左端点int left = 0, right = n - 1;while(left < right){int mid = left + (right - left)/2;if(nums[mid] >= target){right = mid;}else{left = mid+1;}} if(nums[left] != target) return {-1,-1};else ret.push_back(left);// 找右端点left = 0, right = n-1;while(left < right){int mid = left + (right - left + 1)/2;if(nums[mid] > target){right = mid-1;}else{left = mid;}} if(nums[right] != target) return {-1,-1};else ret.push_back(right);return ret;}
};
三、搜索插入位置
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n-1;while(left < right){int mid = (left + right)/2;if(nums[mid] < target){left = mid+1;}else{right = mid;}}if(nums[left] < target) return left+1;else return left;}
};
四、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){right = mid - 1;}else{left = mid;}}return left;}
};
五、山脉数组的峰顶索引
class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int n = arr.size();int left = 1, right = n-2;while(left < right){int mid = (left + right + 1)/2;if(arr[mid] > arr[mid-1]){left = mid;}else{right = mid - 1;}}return left;}
};
六、寻找峰值
class Solution {
public:int findPeakElement(vector<int>& nums) {int n = nums.size();int left = 0, right = n-1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > nums[mid+1]){right = mid;} else{left = mid + 1;} }return left;}
};
七、寻找旋转排序数组中的最小值
class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size(), left = 0, right = n-1;while(left < right){int mid = left + (right - left)/2;if(nums[mid] > nums[n-1]){left = mid + 1;}else{right = mid;}}return nums[left];}
};
八、点名
class Solution {
public:int takeAttendance(vector<int>& records) {int n = records.size();int left = 0, right = n-1;while(left < right){int mid = left + (right - left)/2;if(records[mid] == mid){left = mid+1;}else{right = mid;}}if(left == records[left]) return left+1;else return left;}
};
