LeetCode热题100——二分查找

1. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

// 题解：
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. 搜素二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

// 题解：按照行和最后一列遍历，对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. 在排序数组中查找第一个和最后一个元素位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 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};
}