Binary Search Made Simple

What’s Binary Search All About?

Binary search is one of those core ideas in programming that you’ll see everywhere. If you have a sorted list or array, binary search helps you find what you’re looking for quickly by cutting the list in half over and over again.

How Does It Work?

Let’s say you’re looking for a number in a sorted array. Instead of checking every element one by one (like linear search), binary search starts in the middle.

If the middle value is what you need—great, you’re done! If the value is smaller than your target, you throw away the left half. If it’s larger, toss the right half. Rinse and repeat until you find your target or run out of elements.

Thinking About It Step by Step

Here’s how we break it down:

1. Start with two pointers: left = 0 and right = nums.length - 1.
2. While left <= right:
   • Find the middle index: mid = left + (right - left) / 2
   • If nums[mid] is your target, return mid
   • If nums[mid] < target, move left to mid + 1
   • If nums[mid] > target, move right to mid - 1
3. If nothing is found, return -1

Here’s the Java Code

class Solution {
	public int search(int[] nums, int target) {
		// Set the left and right boundaries
		int left = 0, right = nums.length - 1;

		// Under this condition
		while (left <= right) {
			// Get the middle index and the middle value.
			int mid = left + (right - left) / 2;

			// Case 1, return the middle index.
			if (nums[mid] == target) {
				return mid;
			}
			// Case 2, discard the smaller half.
			else if (nums[mid] < target) {
				left = mid + 1;
			}
			// Case 3, discard the larger half.
			else {
				right = mid - 1;
			}
		}

		// If we finish the search without finding target, return -1.
		return -1;
	}
}
  

How Fast Is Binary Search?

Time Complexity: O(log n)

Every time you check the middle, you’re cutting the list in half. So even if the list is huge, it takes only a few steps to find the value—or confirm it’s not there.

Space Complexity: O(1)

You only need a few variables—like left, right, and mid. That’s it. No extra memory needed.

Pros of Binary Search

• Super fast for large, sorted data.
• Simple to implement once you get the hang of it.
• Works great in many real-world use cases.

But There Are a Few Limitations

• The list has to be sorted. If it’s not, binary search won’t work.
• Not ideal for linked lists or structures without random access.

Where Do We Use Binary Search?

It’s everywhere—from searching names in a contact list, finding a word in a dictionary, optimizing algorithms, to narrowing down answers in coding problems.

Tips for Success

• Always check if the list is sorted first.
• Watch out for off-by-one errors—common in binary search.
• Use test cases with 1 or 2 elements to test your logic.

Binary vs Linear Search

Binary search is fast but needs sorted data. Linear search checks one-by-one, slower for big lists but works on anything. Use binary search when speed matters and you know your data is in order.

FAQs

Can I use binary search on unsorted data?

Nope, the data has to be sorted for binary search to work correctly.

What if the number isn’t in the array?

You’ll reach the end of the loop and return -1—it simply means it’s not there.

Can binary search work on a linked list?

Not really. Linked lists don’t give you direct access to the middle, so binary search is inefficient there.

Do all languages support binary search?

Pretty much. Either through built-in libraries or your own implementation, it’s doable in Java, Python, C++, and more.

How can I avoid bugs when coding binary search?

Test edge cases, double-check your math on mid, and watch the loop condition. Practice helps a lot!

In a Nutshell

Binary search is a must-know tool for every developer. It’s fast, reliable, and shows up all over tech problems. Master it once, and you’ll use it forever.

Approach 2: Find Upper bound

Intuition

Here we introduce an alternative way to implement binary search: instead of looking for target in the array nums, we look for the insert position where we can put target in without disrupting the order.

Generally, we have two inserting ways, insert into the rightmost possible position which we called finding the upper bound, and insert into the leftmost possible position which we called finding the lower bound. We will implement them in the following approaches.

Take the picture below as an example. Assume that we want to insert 9 into array A. If we look for the upper bound, we have to insert 9 to the right of all existing 9s in the array. Similarly, if we look for the lower bound, we have to insert 9 to the left of all existing 9s. (Although we don't have duplicate elements in this problem, having duplicate elements is more common in problems so we would better know this concept in advance!)

Now we start the binary search. Similar to the previous approach, we still use left and right as two boundary indexes. The question is, what is the next step after we find the middle index mid?

1. If nums[mid] < target, the insert position is on mid's right, so we let left = mid + 1 to discard the left half and mid. 2. If nums[mid] = target, the insert position is on mid's right, so we let left = mid + 1 to discard the left half and mid. 3. If nums[mid] > target, mid can also be the insert position. So we let right = mid to discard the right half while keeping mid. Therefore, we merged the two conditions nums[mid] = target and nums[mid] < target and there are only two conditions in the if-else statement!

Once the loop stops, left stands for the insert position and left - 1 is the largest element that is no larger than target. We just need to check if nums[left - 1] equals target. Note this boundary condition where left = 0, which means all elements in nums are larger than target, so there is no target in nums.

Algorithm

1. Initialize the boundaries of the search space: left = 0 and right = nums.size

   Note: The maximum insert position can be nums.size.

2. While there are elements in the range [left, right]:
   • Find the middle index: mid = (left + right) / 2.
   • Compare nums[mid] with target:
   • If nums[mid] <= target, set left = mid + 1 and repeat step 2.
   • If nums[mid] > target, set right = mid and repeat step 2.
3. When the loop ends, left represents the insert position:
   • If left > 0 and nums[left - 1] == target, return left - 1.
   • Otherwise, return -1.

Here’s the Java Code

  
  class Solution {
    public int search(int[] nums, int target) {
        // Set the left and right boundaries
        int left = 0, right = nums.length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        if (left > 0 && nums[left - 1] == target) {
            return left - 1;
        } else {
            return -1;
        } 
    }
}

Complexity Analysis

Let n be the size of the input array nums.

Time Complexity: O(log n)

At each step, the array is divided in half. In the worst-case scenario, we continue splitting the range until there are no elements left. This results in a logarithmic number of steps, so the time complexity is O(log n).

Space Complexity: O(1)

The algorithm uses only a constant amount of space — it keeps track of just three variables: left, right, and mid. No extra memory is used that depends on the input size.

Approach 3: Find Lower bound

Intuition

This approach differs from the classic binary search because we’re specifically searching for the leftmost insert position of the target. To do this, we slightly change the logic in our condition checks:

• If nums[mid] < target: Since mid could also be a valid insert position, we move left = mid + 1. This discards the left half, but keeps mid in play.
• If nums[mid] = target or nums[mid] > target: The correct insert position lies to the left of mid, so we set right = mid, discarding both mid and the right half.

These two cases allow us to merge the conditions nums[mid] == target and nums[mid] > target into a single branch. So the if-else structure only has two conditions, making the logic concise and efficient.

When the loop ends, left represents the insert position, and nums[left] is the smallest element that is greater than or equal to the target.

Note: There’s a special boundary case when left == nums.length. This means every element in the array is smaller than the target, so target doesn’t exist in nums.

Algorithm

1. Initialize the boundaries of the search space: left = 0 and right = nums.length (Note: the maximum insert position can be nums.length).
2. While there are elements in the range [left, right):
   • Calculate the middle index: mid = (left + right) / 2.
   • Compare nums[mid] with target:
     • If nums[mid] >= target, set right = mid and repeat.
     • If nums[mid] < target, set left = mid + 1 and repeat.
3. When the loop ends, left represents the insert position:
   • If left < nums.length and nums[left] == target, return left.
   • Otherwise, return -1.

Here’s the Java Code

class Solution {
    public int search(int[] nums, int target) {
        // Set the left and right boundaries
        int left = 0, right = nums.length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        if (left < nums.length && nums[left] == target) {
            return left;
        } else {
            return -1;
        } 
    }
} 

Complexity Analysis

Let n be the size of the input array nums.

Time Complexity: O(log n)

The array nums is divided in half with each iteration. In the worst-case scenario, we continue this process until the search range becomes empty. This logarithmic reduction leads to a time complexity of O(log n).

Space Complexity: O(1)

The algorithm only needs to track three variables: left, right, and mid, which means it uses a constant amount of space regardless of the input size.

Approach 4: Use built-in tools.

Intuition

After exploring different binary search templates, let’s take a quick look at a more convenient approach that uses built-in functions. Many programming languages offer libraries that simplify binary search.

For instance, C++ provides the <algorithm> library with functions like upper_bound and lower_bound. Similarly, Python has the bisect module with bisect_right and bisect_left. These tools are great for solving standard problems quickly without writing the entire binary search logic manually.

Here's what they do:

• upper_bound in C++ and bisect.bisect_right in Python find the rightmost insertion position. This is similar to the second binary search approach.
• lower_bound in C++ and bisect.bisect_left in Python find the leftmost insertion position. This matches the logic of the third binary search approach.

Once you determine the insertion position using these built-in tools, simply check if the value at that position matches the target.

In this explanation, we’ll demonstrate the method using upper_bound or bisect.bisect_right. Try implementing the alternative with lower_bound or bisect.bisect_left as a practice challenge!

Algorithm

1. Use built-in tools such as upper_bound in C++ or bisect.bisect_right in Python to find the rightmost insertion position idx.
2. Check the element before this position:
   • If idx > 0 and nums[idx - 1] == target, then the target was found — return idx - 1.
   • Otherwise, return -1 to indicate the target is not present.

Here’s the Java Code

class Solution {
public:
    int search(vector& nums, int target) {
        // Find the insertion position `idx`.
        int idx = upper_bound(nums.begin(), nums.end(), target) - nums.begin();

        if (idx > 0 && nums[idx - 1] == target) {
            return idx - 1;
        } else {
            return -1;
        }    
    }
};

Complexity Analysis

Let n be the size of the input array nums.

Time Complexity: O(log n)

The time complexity of the built-in binary search is O(log n) since it divides the search space in half at each step.

Space Complexity: O(1)

The built-in binary search uses only a constant amount of memory, hence the space complexity is O(1).