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 inserted in order to maintain the sorted order. This is an easy-level problem solved efficiently with binary search.

Example

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

Output: 2 (index of 5 in the array)

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

Output: 1 (index where 2 should be inserted)

Code

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 3, 5, 6};
        System.out.println(sol.searchInsert(nums, 5)); // 2
        System.out.println(sol.searchInsert(nums, 2)); // 1
    }
}
            

def search_insert(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return left

# Example usage
nums = [1, 3, 5, 6]
print(search_insert(nums, 5))  # 2
print(search_insert(nums, 2))  # 1
            

function searchInsert(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

// Example usage
const nums = [1, 3, 5, 6];
console.log(searchInsert(nums, 5)); // 2
console.log(searchInsert(nums, 2)); // 1
            

Explanation

• Initialize two pointers: left at the start and right at the end of the array.
• Calculate the middle index, adjusting for each language's syntax.
• If the middle element equals the target, return its index.
• If the middle element is less than the target, search the right half by moving left to mid + 1.
• If the middle element is greater, search the left half by moving right to mid - 1.
• When the loop ends, left points to the insertion position.

Note