Binary Search

Problem Link

Binary Search

Problem Statement

You are given a sorted array of unique integers nums (in ascending order) and an integer target. Your task is to return the index of the target if it exists in the array. If it does not exist, return -1.

The solution must have a runtime complexity of O(log n).

Examples:

• Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
  Output: 4
  Explanation: 9 exists in the array at index 4.

• Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
  Output: -1
  Explanation: 2 is not present in the array.

Constraints:

• 1 <= nums.length <= 10^4

• -10^4 < nums[i], target < 10^4

• All elements in nums are unique.

• The array is sorted in ascending order.

Intuition

Since the array is already sorted and we need to achieve O(log n) time complexity, a linear scan is inefficient. This suggests the use of Binary Search, which is ideal for searching in sorted collections.

Binary Search divides the array into halves to quickly eliminate the portion where the target cannot exist.

Approach

1. Initialize two pointers:
   start = 0, end = nums.length - 1

2. Run a loop while start <= end:
   a. Compute the middle index:
   mid = start + (end - start) / 2 (to avoid integer overflow)

   b. Compare nums[mid] with the target:

   • If equal, return mid

   • If nums[mid] < target, search in the right half: start = mid + 1

   • Else, search in the left half: end = mid - 1

3. If the loop ends and no match is found, return -1.

Code in Java

class Solution {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {
                return mid; // target found
            } else if (nums[mid] < target) {
                start = mid + 1; // search right half
            } else {
                end = mid - 1; // search left half
            }
        }

        return -1; // target not found
    }
}

Time and Space Complexity

• Time Complexity: O(log n)
  Because in each iteration, the search space is halved.

• Space Complexity: O(1)
  No extra space is used apart from a few variables.

Dry Run

Input:
nums = [-1, 0, 3, 5, 9, 12], target = 9

Steps:

• start = 0, end = 5

• mid = (0 + 5) / 2 = 2 → nums[2] = 3
  Since 3 < 9 → move to right half → start = 3

• start = 3, end = 5

• mid = (3 + 5) / 2 = 4 → nums[4] = 9
  Match found → return 4

Output: 4

Conclusion

Binary Search is a fundamental algorithm that should be your default approach whenever you see a sorted array and the need to search an element efficiently. It reduces the time complexity from O(n) to O(log n) using a simple divide-and-conquer technique.

This implementation uses the iterative approach, which is both time and space efficient.