35. Search Insert Position

// LeetCode URL: https://leetcode.com/problems/search-insert-position/
/**
 * Binary Search
 *
 * We are trying to find the index of number equal to target or index of number
 * just larger than target.
 *
 * Time Complexity: O(log N)
 *
 * Space Complexity: O(1)
 *
 * N = Lenght of the input array.
 */
class Solution {
    public int searchInsert(int[] nums, int target) throws IllegalArgumentException {
        if (nums == null) {
            throw new IllegalArgumentException("Inout array is null");
        }
        if (nums.length == 0) {
            return 0;
        }

        int left = 0;
        int right = nums.length; // This is valid as the target can be larger than all numbers in the array.

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid; // We are trying to find the index of number equal to target or index of number
                             // just larger than target.
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}