Whenever you see "sorted array" think binary search.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.

This is a typical binary search problem with an added requirement to return the insertion index.

If you trace a binary search start,end,mid pointers you will see that if the search is not successful the start pointer will be pointing to the insertion location.

Code: Select all

```
public int searchInsert(int[] nums, int target) {
if (nums.length == 0) return 0;
int start = 0;
int end = nums.length - 1;
while(start <= end) {
int mid = (start + end) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
```