35. 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.

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

Approach 1: Binary Search

🔍 Intuition

Looking at the nature of the problem, it’s clear that binary search is a perfect fit. Binary search is a powerful algorithm used to find the position of a target value in a sorted array.

The idea is simple: at each step, you compare the middle element of the current range to your target.

• If the target equals the middle element, you’ve found your answer.
• If the target is smaller, search the left half.
• If the target is larger, search the right half.

🧭 Step-by-Step

To keep track of where we're searching, we use two pointers: left and right. Initially, left = 0 and right = n - 1.

While left <= right:

• Find the middle index: pivot = (left + right) / 2
• If nums[pivot] == target, you’ve found it.
• If target < nums[pivot], move the search to the left: right = pivot - 1
• If target > nums[pivot], search the right: left = pivot + 1

If the loop ends without finding the target, it means the value isn’t in the array. At that point, left will point to the correct index to insert the target if needed.

⚠️ Handling Integer Overflow

A common issue in languages like Java or C++ is that (left + right) / 2 can cause overflow when the values are too large (exceeding 2³¹−1).

To avoid this, calculate the pivot like this:

• pivot = left + (right - left) / 2; (safe and preferred)
• pivot = (left + right) >> 1; (bitwise method, slightly faster)

🧪 Algorithm

1. Initialize: left = 0, right = n - 1
2. While left <= right:
   • Calculate pivot
   • If nums[pivot] == target: return pivot
   • If target < nums[pivot]: right = pivot - 1
   • Else: left = pivot + 1
3. Return left as the insertion position if not found

Java code

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

📈 Complexity Analysis

Time Complexity: O(logN)
Each time, we divide the problem in half. According to the Master Theorem:

T(N) = aT(N/b) + Θ(Nd)

Here, a = 1 (one subproblem), b = 2 (size halves), and d = 0 (constant time). This leads us to Case 2 of the theorem, giving us: O(logN).

Space Complexity: O(1)
No extra space is used—just a few pointers. Very space-efficient!