LeetCode 35 搜索插入位置简单解法 && 二分查找 Leetcode

问题描述给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:

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

示例 2:

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

示例 3:

输入: [1,3,5,6], 7 输出: 4

示例 4:

输入: [1,3,5,6], 0 输出: 0

分析

target 插入位置就是它大于左值且小于右值的地方。写代码时可以反过来考虑，nums[i] 终于大于等于 target 值的地方，就是插入位置；
相等时可以直接返回该索引所在位置。

代码

class Solution { public: int searchInsert(vector& nums, int target) { int size = nums.size(); for (int i = 0; i < nums.size(); i++){ if (nums[i] >= target) return i; } return size; } };

遇到的问题其实我的 for 循环里边，一开始是有这样一条语句：if (nums[++i] >= target) return i;
【LeetCode 35 搜索插入位置简单解法 && 二分查找】做完看起来呢，是毫无必要对不对。但是自己设计逻辑就会有疏漏。这样做不仅没必要去对比 nums[i] 的下一个与 target 的关系。而且会有溢出错误：AddressSanitizer: heap-buffer-overflow on address。没有 ++i 的情况就是这样。
补上二分查找

class Solution { public: int searchInsert(vector& nums, int target) { int mid = 0; int head = 0; int last = nums.size() - 1; while (head <= last) { mid = (head + last) / 2; if (target < nums[mid]) { last = mid - 1; } else if (target > nums[mid]) { head = mid + 1; } else return mid; } if (target <= nums[head]) return head; return head; } };