Binary Search - Search Insert Position

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.

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

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

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

Constraints:

1 <= nums.length <= 10⁴
-10⁴ < nums[i], target< 10⁴
nums contains distinct values sorted in ascending order.
-10⁴ <= target <= 10⁴

Solution 1 - Using binary search

In this approach, we will apply Binary Search algorithm, since the input array is sorted in ascending order, we will use two pointers left and right to point to left and right end of array, and then using a while loop, compute the middle index mid = $[\begin{matrix} left + right \\ _____________ \\ 2 \end{matrix}]$ , then check if the element at mid index, based on the element found at mid index, we can draw three conclusions.

If the element at mid index is the target, then return the mid index, since the element is same, it can be inserted at this position.
If the element at mid index is greater than target, since the array is sorted in ascending order, this means that the target lies on left half of the array, so we will update right index to mid-1.
If the element at mid index is less than target, since the array is sorted in ascending order, this means that the target lies on right half of the array, so we will update left index to mid+1.

If that target is not found, we will return left index as answer, this is where the target element can be inserted.

public class SearchInsertPosition { static 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) { right = mid-1; } else { left = mid +1; } } return left; } public static void main(String[] args) { System.out.println(searchInsert(new int[]{1,3,5,6}, 5)); System.out.println(searchInsert(new int[]{1,3,5,6}, 2)); System.out.println(searchInsert(new int[]{1,3,5,6}, 7)); } }

Complexity Analysis:

Time complexity: Above code runs in O(log n) time where n is the length of input array nums.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Complexity Analysis: