leetcode 二分法总结

按照35，34的顺序刷题能更好的理解二分法！！！！

35 ���索插入位置

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

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2输出: 1

 注意：

• nums 为 无重复元素 的 升序 排列数组

  1.题目规定不会存在重复数字，所以如果数组中存在目标数字，返回值就是mid的值，因为二分法执行完后，mid指向的一定是目标数字位置（目标数字存在且无重复的情况）。

  2.如果数组中不存在，为了方便理解，我们假设先按序插入目标数字，这样我们只需要找到排序后target的位置记左边界。（实际上是定位到第一个大于或等于target的数的位置 ）

  实际上，对于边界我们往往分开区间和闭区间（如下图，target = 8时，实际上我们要boundary -> nums[i] = 9，这是闭区间，即左边界就是boundary指向的位置，如果是开区间那么

  boundary -> nums[i] = 7，但最后插入的话要 + 1），实际上这也和判断条件有关，同样的执行代码，如果是while(left 1) + left; if (target = target)) { right = mid - 1; ans = mid; } else { left = mid + 1; } } return ans; } vector searchRange(vector& nums, int target) { int leftIdx = binarySearch(nums, target, true); int rightIdx = binarySearch(nums, target, false) - 1; if (leftIdx