35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
题目来源：力扣（LeetCode）
二分法查找思路
能否写出：能写出。
时间：20多分钟
思路：
大部分思路与二分法查找思路一样，从小白开始刷算法 二分法篇 leetcode.704
后增加一个循环结束后的处理逻辑
- 循环结束后，如果目标元素不在数组中，则根据最后的起始位置 start 判断目标元素应该插入的位置：
- 如果数组中的元素都比目标元素小，则插入位置为
start + 1。 - 否则，插入位置为
start。
- 返回插入位置。
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public int searchInsert(int[] nums, int target) { int start = 0; int end = nums.length - 1; while (start < end) { int middle = start + (end - start) / 2; if (nums[middle] == target) { return middle; } if (nums[middle] > target) { end = middle; } else { start = middle + 1; } } if (nums[start] < target) { return start + 1; } else { return start; } } }
时间复杂度： O(log n)
空间复杂度：O(1)
