35. Search Insert Position
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
给定一个排好序的数组，数组里面的元素不会重复。在给定一个目标数值。如果找到了目标就返回其下标，如果没找到目标就返回其可能按顺序插入所在的位置
You must write an algorithm with O(log n) runtime complexity.
时间复杂度O(log n)
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
如果不存在的话就返回最大的比他小的元素所在的下标加一
Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
这个下标可能会超过下标的范围。所以返回值的取值返回应该是[0, len(nums)+1]
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104
思考
从时间复杂度来看这又是一题需要用到二分法的问题。
用迭代，使用左右双指针，不断缩紧左右双指针之间的位置。
最后判断如果双指针归位同一个下标的时候，如果该下标的value和target相等，则返回当前下标。如果小于则返回index+1。如果大于则返回index-1。
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1
ans = 0
while (left < right):
mid = int((left+right)/2)
if nums[mid]==target:
return mid
elif nums[mid]>target:
right = mid-1
# ans = right
elif nums[mid]<target:
left = mid+1
# ans = left
if nums[left]<target:
return left+1
else:
return left
这道题比较简单，我尝试使用了迭代的方法去计算。
难点就在于最后如何判断返回值的位置在哪里。
我在迭代的时候，退出条件是left和right相等的时候退出。
当left下标的value等于target的时候直接返回target，当小于target的时候返回left+1，当大于的时候也直接返回left。
答案解析
int searchInsert(int* nums, int numsSize, int target) {
int left = 0, right = numsSize - 1, ans = numsSize;
while (left <= right) {
int mid = ((right - left) >> 1) + left; #这边是C的代码，所以采用位运算达到整除的效果，比较好
if (target <= nums[mid]) {
ans = mid; #相当于最后也是定位到最想等的情况，判断下标返回值。当target小于mid元素的时候，记录mid。就相当于每次更新了最右可能位置的index
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
和我一样使用的解题思路，但是最后迭代的时候比较漂亮。可以学习一下
总结
迭代还是不太明白。需要继续学习。
