LeetCode[简单] 搜索插入位置

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

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

思路：类似与二分查找

唯一需要注意的是，搜索插入位置

在二分查找的过程中，如果 nums[mid] < target，则将 low 更新为 mid + 1，因此在二分查找结束之后有 nums[low] ≥ target。当目标值不存在时，二分查找结束之后有 nums[low] > target。又由于当 nums[mid] ≥ target 时不可能将 low 更新为比 mid 大的值，因此在二分查找结束之后有nums[low−1] < target。

因此在二分查找结束之后有 nums[low−1] < target < nums[low]，low 即为目标值在数组中的插入位置。

public class Solution {public int SearchInsert(int[] nums, int target) {int low = 0, high = nums.Length - 1;int mid = (high + low)/2;while(low <= high){mid = (low + high)/2;if(nums[mid] == target)return mid;else if(nums[mid] > target)high = mid - 1;elselow = mid + 1;}return low;}
}