LeetCode热题100（搜索插入位置）

题目描述

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

请必须使用时间复杂度为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。