Problem Overview

You are given a sorted array of distinct integers nums and a target value target.
Your task is to find the index of the target in the array if it exists.
If it does not exist, return the index where it would be inserted to maintain the sorted order.

Example 1:

Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Explanation: 5 exists at index 2.

Example 2:

Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Explanation: 2 should be inserted at index 1 to maintain the sorted order.

Example 3:

Input: nums = [1, 3, 5, 6], target = 7
Output: 4
Explanation: 7 is greater than all elements, so it should be inserted at the end.

Example 4:

Input: nums = [1, 3, 5, 6], target = 0
Output: 0
Explanation: 0 is smaller than all elements, so it should be inserted at the beginning.

---

Intuition / Approach

Since the array is sorted, we can efficiently find the position using Binary Search instead of a linear scan.

The binary search helps us decide whether to move left or right depending on whether the target is smaller or larger than the middle element.

If we find the target, we return its index directly.
If not found, the left pointer (low) will end up at the correct position where the target should be inserted.

---

Step-by-Step Algorithm Explanation

1. Initialize two pointers:
   • low = 0
   • high = nums.length - 1
2. While low <= high:
   • Calculate the middle index: mid = low + (high - low) / 2
   • If nums[mid] == target, return mid (found exact match).
   • If nums[mid] < target, move to the right half by setting low = mid + 1.
   • Otherwise, move to the left half by setting high = mid - 1.
3. If the loop ends and the target is not found, low will represent the correct insert position.
4. Return low.

---

Example Walkthrough

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

Step	low	high	mid	nums[mid]	Comparison	Action
1	0	3	1	3	3 > 2	Move left → high = 0
2	0	0	0	1	1 < 2	Move right → low = 1

Now low = 1 and high = 0, loop ends.
So, insert position = 1.

---

Java Code Implementation

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (nums[mid] == target) {
                return mid; // Target found
            } else if (nums[mid] < target) {
                low = mid + 1; // Search in the right half
            } else {
                high = mid - 1; // Search in the left half
            }
        }
        
        // If target not found, 'low' is the insert position
        return low;
    }
}

---

Complexity Analysis

1. Time Complexity:
   The algorithm performs a binary search, cutting the search space in half each iteration.
   Therefore, O(log n) time complexity.
2. Space Complexity:
   Only a few variables (low, high, and mid) are used, requiring constant space.
   Therefore, O(1) space complexity.

---

Alternative Approach: Linear Search (Less Efficient)

If we traverse the array linearly:

• For each element, check if nums[i] >= target
• Return i when condition matches.
• If loop finishes, return nums.length.

This approach takes O(n) time, which is slower for large arrays.
Hence, binary search is preferred.