Binary Search | Leetcode 704 | Explained in Python

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Here’s the [Problem Link] to begin with.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

• 1 <= nums.length <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

OPTIMAL SOLUTION

1. Intuition & Approach (Breaking it Down Step-by-Step)

Understanding the Problem

We are given a sorted array (nums) and a target integer (target). Our goal is to determine the index of target in nums. If target is not found, we return -1.

Why Binary Search?

Instead of checking each element one by one (O(N) time complexity) like linear search, we can leverage the fact that the array is sorted and efficiently reduce our search space by half in each step.

How Binary Search Works

1. Set two pointers (low and high) at the beginning (0) and end (n-1) of the array.
2. Find the middle index (mid) of the current search range.
3. Compare nums[mid] with target:
   • If nums[mid] == target, we return mid (found the target).
   • If nums[mid] < target, it means target must be on the right half, so we move low = mid + 1.
   • If nums[mid] > target, it means target must be on the left half, so we move high = mid – 1.
4. Repeat the process until low > high (which means target is not present in the array).

This approach eliminates half of the remaining elements at each step, making it extremely fast compared to scanning the array linearly.

2. Code Implementation

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        low = 0
        high = n - 1

        while low <= high:
            mid = (low + high) // 2  # Find the middle index

            if nums[mid] == target:
                return mid  # Target found, return index

            elif nums[mid] < target:
                low = mid + 1  # Move to the right half

            else:
                high = mid - 1  # Move to the left half

        return -1  # Target not found

3. Code Explanation (High-Level Overview)

Step 1: Initialize Search Range

• We define low = 0 (start) and high = n – 1 (end) to keep track of our search space.

Step 2: Loop Until low Exceeds high

• The loop runs until low <= high, ensuring we continue searching as long as there is a valid range.

Step 3: Compute the Middle Index

• The middle index is calculated using: mid = (low+high) / 2
• This splits the array in half at each step.

Step 4: Compare nums[mid] with target

1. If nums[mid] == target, we return mid (target found).
2. If nums[mid] < target, move to the right half (low = mid + 1).
3. If nums[mid] > target, move to the left half (high = mid – 1).

Step 5: Return -1 if Target is Not Found

• If the loop exits without finding the target, we return -1 (indicating absence in the array).

4. Dry Run (Step-by-Step Execution)

Example 1

Execution Process

Final Output:

Example 2 (Target Not Found)

• Since low (2) > high (1), loop terminates and returns -1 (target not found).

Final Output:

5. Time and Space Complexity Analysis

Time Complexity:

• At each step, we divide the search space in half.
• The maximum number of steps required to find an element in an array of size N is log₂(N).
• Time complexity: O(log⁡N)
• This is significantly faster than a linear search (O(N)).

Space Complexity:

• The algorithm only uses a few integer variables (low, high, mid).
• No extra memory is used, so space complexity is: O(1)

6. Edge Cases to Consider

1. Target is the First or Last Element

Expected Output: 0

Expected Output: 4

2. Target is Not in the Array

Expected Output: -1 (not found)

3. Empty Array

Expected Output: -1 (no elements to search)

4. Array Contains One Element

Expected Output: 0 (found at index 0)

5. Large Input Case

Binary search finds it in log₂(10⁶) ≈ 20 comparisons instead of 1,000,000 comparisons in linear search.

Conclusion

✅ Why This Solution is Optimal?

• O(log N) complexity makes it highly efficient for large datasets.
• O(1) space complexity (no extra storage required).
• Works for any sorted array, regardless of size.
• Much faster than linear search, especially for large inputs.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.