35.搜索插入的位置

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

可以采用分治策略（Divide，Conquer，Combine），原问题划分成规模更小的形式相同的子问题（递归情况），递归至足够小规模（基本情况）求解子问题，子问题的解组合成原问题的解。

方法1：很直接

class Solution { public int searchInsert(int[] nums, int target) { int i=0; while(i<nums.length){ if(nums[i]>=target) break; i++; } return i; } }

时间复杂度：O(N) 空间复杂度：O(1)

方法2：二分查找

public class Solution { public int searchInsert(int[] nums, int target) { int len = nums.length; if (len == 0) { return 0; } if (nums[len - 1] < target) { return len; } int left = 0; int right = len - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } }

时间复杂度：O(logN) 空间复杂度：O(1)

待修改 想把nums[middle]==target 情况拿出来，希望在不触底的情况下得到结果以提高运行速度，但数据情况比较多 ，例如[1,3,5,6] 0不通过待修改。

class Solution { public int searchInsert(int[] nums, int target) { if(nums.length==0) return 0; if(nums[nums.length-1]<target) return nums.length; int left=0; int right=nums.length-1; int middle=0;//先定义并初始化 再循环内改变 //在范围内情况，已去掉特例 while(left<right){ //!= 还要考虑right<left的可能... middle=(left+right)/2; if(nums[middle]<target) left=middle+1; else if(nums[middle]>target) right=middle-1; else //把等于拿出来在不用遍历到底的情况下可直接得到 return middle; } /* 在很少递归下找到相等直接return 究极情况下，由三元素规模递归到两元素并且left==middle==right-1； 1）存在nums[middle]==target 直接return left 或者middle 或 （nums[middle]<target && nums[right]==target 递归中right取值OK）程序跳出循环， 此时应该直接return left 或right 2)不存在相等元素，跳出循环 if(nums[middle]<target) return middle+1; else if(nums[middle]>target) return middle; */ if(nums[middle]<target && nums[right]==target) return left; else if(nums[middle]<target) return middle+1; else return middle; } }