广州市做企业网站,深圳网站建设公司电话,新乡seo优化,做网站要多少的服务器给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。 思路#xff1a;类似与二分查找
唯一需要注意的是#xff0c;搜索…给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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;}
}
