https://leetcode.com/problems/search-insert-position/description/
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.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 1:
Input: [1,3,5,6], 0
Output: 0
time complexity: o(logn)
space complexity: o(1)
1 public int searchInsert(int[] nums, int target) {
2 if (nums == null || nums.length ==0) return 0 ;
3 int left = 0, right = nums.length -1 ;
4 //corner case:
5 if (nums[left]>target){
6 return left ;
7 }
8 if (nums[right]<target){
9 return right + 1 ;
10 }
11 while(left + 1 < right){
12 int mid = left + (right - left )/2 ;
13 if (nums[mid] == target) return mid ;
14 else if(nums[mid]<target){
15 left = mid ;
16 } else {
17 right = mid ;
18 }
19 }
20 //== now: 1) still have not found it 2) left and right sits right next to each other
21 //post processing
22 if (nums[left] == target) {
23 return left ;
24 }
25 if (nums[right] == target){
26 return right;
27 }
28 //remember left and right next to each other
29 if(nums[left]<target && target < nums[right]){
30 return left + 1 ;
31 }
32 return -1 ;
33 }
