题目描述
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为O(log n)的算法。
代码:
class Solution { public int searchInsert(int[] nums, int target) { int left = 0; int right = nums.length - 1; while(left <= right){ int temp = (right + left) /2; if(nums[temp] > target){ right = temp - 1; }else if(nums[temp] < target){ left = temp + 1; }else{ return temp; } } return left; } }思路复盘:
1.二分法的思路,注意最后返回的是left,分析原因,此时left > right才会跳出循环,第一种情况left = temp+1之后导致的跳出循环,target大于left和right所在的位置的值,往后移一位便是插入的位置。第二种情况,right = temp - 1导致的,target小于left和right所在的位置,返回之前的right所在的位置,也就是left。