[TOC] ## 二分搜索模板 ## 示例 #### [704\. 二分查找](https://leetcode-cn.com/problems/binary-search/) 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 ``` class Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } }; ``` #### [61.搜索区间](https://www.lintcode.com/problem/search-for-a-range/description) ``` class Solution { public: /** * @param A: an integer sorted array * @param target: an integer to be inserted * @return: a list of length 2, [index1, index2] */ vector<int> searchRange(vector<int> &A, int target) { // write your code here vector<int> result; int start = -1; int end = -1; int left = 0; int right = A.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (A[mid] == target) { start = mid; end = mid; while (start - 1 >= 0 && A[start - 1] == target) start--; while (end + 1 < A.size() && A[end + 1] == target) end++; break; } else if (A[mid] < target) left = mid + 1; else right = mid - 1; } result.push_back(start); result.push_back(end); return result; } }; ``` #### [35\. 搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/) 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 ``` class Solution { public: int searchInsert(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int mid = 0; while (left <= right) { mid = left + (right - left) / 2; if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return target < nums[mid] ? mid : mid + 1; } }; ``` #### [240\. 搜索二维矩阵 II](https://leetcode-cn.com/problems/search-a-2d-matrix-ii/) 示例: 现有矩阵 matrix 如下： [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5，返回 true。 给定 target = 20，返回 false。 限制： 0 <= n <= 1000 0 <= m <= 1000 ```cpp class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty()) return false; int row_len = matrix.size(); int col_len = matrix[0].size(); int row = 0; int col = col_len - 1; while (row < row_len && col >= 0) { int value = matrix[row][col]; if (target == value) return true; if (target < value) { col--; } else { row++; } } return false; } }; ``` #### [238\. 除自身以外数组的乘积](https://leetcode-cn.com/problems/product-of-array-except-self/) 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。 示例: 输入: [1,2,3,4] 输出: [24,12,8,6] 提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。 说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。 进阶： 你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。） ```cpp class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); int left = 1; // 从左边累乘 int right = 1; // 从右边累乘 vector<int> result(n, 1); for (int i = 0; i < n; ++i) { //最终每个元素其左右乘积进行相乘得出结果 result[i] *= left; //乘以其左边的乘积 left *= nums[i]; result[n - 1 - i] *= right; //乘以其右边的乘积 right *= nums[n - 1 - i]; } return result; } }; ```