// 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

public class Solution {
    public int searchInsert(int[] A, int target) {
 		int pos = 0;

 		for(int i = 0; i < A.length; i++){
 			if(A[i] == target){
 				return i;
 			}

 			if(A[i] > target){
 				return pos;
 			}

 			if(A[i] < target){
 				pos = i + 1;
 			}
 		}      

 		return pos; 
    }
}
@@ -386,72 +386,240 @@
  %7B%0A 
-%09%09int pos = 0;%0A%0A %09%09for(int i = 0; i %3C A.length; i++)%7B%0A %09%09%09
+       int len = A.length;%0A        if(len == 0)%7B%0A            return 0;%0A        %7D%0A        int start = 0;%0A        int end = len - 1;%0A        while(start + 1 %3C end)%7B%0A            int mid = start + (end - start) / 2;%0A            
 if(A%5B
-i
+mid
 %5D ==
@@ -633,42 +633,64 @@
 )%7B%0A 
-%09%09%09%09return i;%0A %09%09%09%7D%0A%0A %09%09%09
+               return mid;%0A            %7Delse 
 if(A%5B
-i%5D %3E
+mid%5D %3C
  tar
@@ -700,41 +700,131 @@
 )%7B%0A 
-%09%09%09%09return pos;%0A %09%09%09%7D%0A%0A %09%09%09
+               start = mid;%0A            %7Delse%7B%0A                end = mid;%0A            %7D%0A        %7D%0A        %0A        
 if(A%5B
-i
+end
 %5D %3C 
@@ -837,58 +837,153 @@
 )%7B%0A 
-%09%09%09%09pos = i + 1;%0A %09%09%09%7D%0A %09%09%7D      %0A%0A %09%09return pos; 
+           return end + 1;%0A        %7Delse if(A%5Bstart%5D %3E= target)%7B%0A            return start;%0A        %7Delse%7B%0A            return start + 1;%0A        %7D
 %0A   

update search-insert-position using binary search