1. 搜索插入位置

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

// 題解：
int searchInsert(vector<int>& nums, int target) {if (nums.empty()) {return 0;}int left = 0;int right = nums.size() - 1;while (left < right) {int mid = (left + right) >> 1;if (nums[mid] < target) {left = mid + 1;} else {right = mid;}}return right ;
}

2. 搜素二維矩陣

給你一個(gè)滿足下述兩條屬性的 m x n 整數(shù)矩陣：每行中的整數(shù)從左到右按非嚴(yán)格遞增順序排列。每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)。
給你一個(gè)整數(shù) target ，如果 target 在矩陣中，返回 true ；否則，返回 false 。

// 題解：按照行和最后一列遍歷，對(duì)row和col加減
bool searchMatrix(vector<vector<int>>& matrix, int target) {if (matrix.empty()) return false;int rows = matrix.size();if (matrix[0].empty()) return false;int cols = matrix[0].size();int row = 0;int col = cols - 1;while (col < cols && col >= 0 && row < rows && row >= 0) {if (matrix[row][col] < target) row++;else if (matrix[row][col] > target) col--;else return true;}return false;
}

3. 在排序數(shù)組中查找第一個(gè)和最后一個(gè)元素位置

給你一個(gè)按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。請(qǐng)你找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。
如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。
輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

// 題解：兩次二分法找到左和右
vector<int> searchRange(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int first_idx = -1;int last_idx = -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 {first_idx = mid;right = mid - 1;}}left = 0;right = nums.size() - 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 {last_idx = mid;left = mid + 1;}}return {first_idx, last_idx};
}