给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
输入: nums = [1,3,5,6], target = 5 输出: 2输入: nums = [1,3,5,6], target = 2 输出: 1输入: nums = [1,3,5,6], target = 7 输出: 4输入: nums = [1,3,5,6], target = 0 输出: 0输入: nums = [1], target = 0 输出: 0
首先,此题对算法时间复杂度有要求,要求log n,我们想到用二分法来解决这个问题。
使用二分法时,要设置左边界和右边界,left 和 right。
class Solution { public int searchInsert(int[] nums, int target) { // int mid = nums.length / 2 ; // while(1){ // if(nums[mid] < target){ // mid = mid + (nums.length() - mid)/2; // } // else if(nums[mid] > target){ // mid = mid / 2; // } // else if(nums[mid] == target){ // return mid; // } // else{ // return mid + 1; // } // } int n = nums.length; int left = 0, right = n - 1, ans = n; //ans用来保存最终结果 while(left <= right){ int mid = (right - left) / 2 + left; if(target <= nums[mid]){ //目标值在左半部分 ans = mid; right = mid - 1; //右边界移动到mid位置 }else{ left = mid + 1; //目标值在右半部分,左边界移动到mid位置 } } return ans; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)