1. Understanding the Problem

You are given an array of integers called nums which is sorted in ascending order, and an integer target.

Your task is to write a function that searches for the target inside nums. If the target exists, return its index. If the target does not exist, return -1.

The Core Constraint:

You must write an algorithm with O(log N) runtime complexity. This is the critical rule that prevents you from just checking every number one by one.

Quick Examples

• nums = [-1, 0, 3, 5, 9, 12], target = 9 — Returns 4. The number 9 exists at index 4.
• nums = [-1, 0, 3, 5, 9, 12], target = 2 — Returns -1. The number 2 is nowhere in the array.

2. The Naive Approach: Linear Search

If you ignore the O(log N) constraint, the easiest way to find the target is to simply start at index 0 and check every single element until you find the target or reach the end of the array.

Trade-off Analysis

While this works, it ignores a massive advantage: the array is already sorted.

• Time Complexity: O(N) — If the array has 10 million elements, you might have to check 10 million times.
• Space Complexity: O(1) — It is memory efficient, but incredibly slow for large datasets.

3. The Optimal Approach: The "Dictionary" Method

Think about how you look up a word in a physical dictionary. You don't read page 1, page 2, page 3 until you find it. You open the book exactly in the middle. If your word comes alphabetically after the middle page, you instantly rip the left half of the book away in your mind. You just eliminated 50% of your work in a single step.

This is exactly how Binary Search works. We use two pointers (left and right) to establish a search boundary. We look at the exact middle of that boundary. If the middle number is too small, we move our left boundary up. If the middle number is too big, we move our right boundary down. We repeat this until we find the target or the boundaries cross (meaning the target doesn't exist).

4. The Logic Step-by-Step

1. Initialize a left pointer at the start of the array (index 0).
2. Initialize a right pointer at the end of the array (length - 1).
3. While left is less than or equal to right:
   • Calculate the mid index. (Pro-tip: to avoid integer overflow in languages like Java or C++, use left + (right - left) / 2 instead of (left + right) / 2).
   • Check the value at nums[mid]:
     • If it equals the target: You found it! Return mid.
     • If it is less than the target: The target must be to the right. Move the left pointer to mid + 1.
     • If it is greater than the target: The target must be to the left. Move the right pointer to mid - 1.
4. If the loop finishes and you haven't returned anything, the target is not in the array. Return -1.

5. Complexity Analysis

• Time Complexity: O(log N) — Because we are halving the search space with every single step, an array of 1,000,000 elements only takes a maximum of 20 guesses to find the target. This is exponentially faster than O(N).
• Space Complexity: O(1) — We only use three integer variables (left, right, mid), meaning this algorithm requires virtually zero extra memory.

6. Code Implementations

Expand the sections below to see the optimal O(log N) time and O(1) space implementation in your preferred programming language.

class Solution:
    def search(self, nums, target):
        left = 0
        right = len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
                
        return -1

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            // Prevents integer overflow for extremely large arrays
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
}

#include <vector>

class Solution {
public:
    int search(std::vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        
        while (left <= right) {
            // Prevents integer overflow for extremely large arrays
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
};

7. Conclusion: You Are Ready

Congratulations, you now possess one of the most powerful algorithms in computer science. Binary Search is much more than just a way to find a number; it is a mental model for optimizing any problem where the search space is sorted or predictable. Whenever an interviewer hands you a problem involving "sorted arrays," your brain should immediately flag O(log N) as the target time complexity. Memorize this template, practice finding the mid point safely, and you will ace these questions effortlessly!