Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0
四点要素:
1. start + 1 < end
2. start + (end - start) / 2
3. A[mid] ==, <, >
4. A[start] A[end] ? target
把题目逻辑想清楚，其实就是找出多少数比target小的，也可以想成找第一个大于等于目标数的位置。
注意中间那块是模板。
public class Solution { public int searchInsert(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int start = 0; int end = nums.length - 1; int mid; if(target < nums[0]) { return 0; } //find the last number less than target while (start + 1 < end) { mid = start + (end - start) / 2; if (nums[mid] == target) { end = mid; } else if (nums[mid] < target) { start = mid; } else { end = mid; } } if (nums[end] == target) { return end; } if(nums[end] < target) { return end + 1; } if(nums[start] == target) { return start; } return start + 1; } }
2. find the first position >= target
public class Solution { public int searchInsert(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int start = 0; int end = nums.length - 1; int mid; //find the first position >= target while (start + 1 < end) { mid = start + (end - start) / 2; if (nums[mid] == target) { end = mid; } else if (nums[mid] < target) { start = mid; } else { end = mid; } } if (nums[start] >= target) { return start; }else if (nums[end] >= target) { return end; }else { return end+1; } } }
Reference:
1. http://www.jiuzhang.com/solutions/search-insert-position/
Leetcode 35. Search Insert Position
原文：http://www.cnblogs.com/anne-vista/p/5132190.html