Search Insert Position

Problem Statement:

Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5 Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2 Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7 Output: 4

Solution:

Very classic application of binary search.

• We are looking for the minimal k value satisfying nums[k] >= target, and we can just copy-paste our template.
• Notice that our solution is correct regardless of whether the input array nums has duplicates.
• Also notice that the input  target might be larger than all elements in nums and therefore needs to placed at the end of the array.
  • That’s why we should initialize right = len(nums) instead of right = len(nums) - 1.

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