Binary Search Explained: A Beginner's Guide With Real Examples

Question 1 : Classic Binary Search (Find the Target)

Given a sorted array of integers and a target value, return the index of the target if it exists in the array. If it doesn't exist, return -1.

Example:

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

Binary Search Code in Java

public class ClassicBinarySearch {
    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            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;
    }
}

Tracing the example: left = 0, right = 5. First mid = 2, nums[2] = 3, which is less than 9, so left moves to 3. Now left = 3, right = 5, mid = 4, nums[4] = 9 that's a match, return 4. Two comparisons, done.

Time and Space Complexity

• Time: O(log n) every step throws away half of what's left to search.
• Space: O(1) only a few variables (left, right, mid) are used, no matter how big the array is.

Any Other Optimal Approach?

This is already the optimal approach for this exact question you can't reliably do better than O(log n) on a plain sorted array without extra information. A hash map lookup could find the target in O(1) time, but that requires building the hash map first (O(n) time and space), so it's only worth it if you're searching the same array repeatedly.

Question 2 : First and Last Occurrence of a Number

Given a sorted array that may contain duplicate values, find the first and last position of a given target value. If the target isn't found, return [-1, -1].

Example:

Input: nums = [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]

Binary Search Code in Java

public class FirstAndLastOccurrence {
    public static int[] searchRange(int[] nums, int target) {
        int first = findBoundary(nums, target, true);
        int last = findBoundary(nums, target, false);
        return new int[]{first, last};
    }
    private static int findBoundary(int[] nums, int target, boolean findFirst) {
        int left = 0;
        int right = nums.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid; // remember this match, but keep searching
                if (findFirst) {
                    right = mid - 1; // keep looking further left
                } else {
                    left = mid + 1; // keep looking further right
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}

Tracing the example: for the "first" search, we find nums[4] = 8 first, save result = 4, but instead of stopping, we shrink right to keep looking left this leads us to nums[3] = 8 too, saving result = 3 and the search eventually confirms there's nothing further left. For "last," the same idea runs in the opposite direction, ending on result = 4. Final output: [3, 4].

Time and Space Complexity

• Time: O(log n) we run two separate binary searches, but two times a logarithm is still just a logarithm.
• Space: O(1) same handful of variables as the classic version.

Any Other Optimal Approach?

You could find one occurrence with a normal binary search in O(log n) and then walk left and right from there checking neighbors but in the worst case (like an array that's entirely the target value), that walk becomes O(n), which defeats the purpose. The two-boundary-search approach above stays reliably O(log n) no matter what, which is why it's the preferred solution.

Question 3 : Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be inserted to keep the array sorted.

Example:

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

Binary Search Code in Java

public class SearchInsertPosition {
    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            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 left; // this is exactly where target would be inserted
    }
}

Tracing the example: left = 0, right = 3. mid = 1, nums[1] = 3, which is bigger than 2, so right = 0. Now left = 0, right = 0, mid = 0, nums[0] = 1, which is smaller than 2, so left = 1. Now left = 1 > right = 0, loop ends. Return left = 1 which is exactly where 2 belongs, between 1 and 3.

Time and Space Complexity

• Time: O(log n)
• Space: O(1)

Any Other Optimal Approach?

There isn't a faster general approach for a plain sorted array this is the standard, optimal way to solve it. The only real "trick" worth knowing is realizing that left naturally ends up at the correct insertion point once the loop finishes, so you don't need any extra logic after the search the same loop that searches for the target also happens to calculate the insertion point for free.

Question 4 : Search in a Rotated Sorted Array

A sorted array has been "rotated" at some unknown point imagine cutting a sorted deck of cards and putting the bottom half on top. Given this rotated array and a target value, find the target's index or return -1 if it isn't present.

Example:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

Binary Search Code in Java

public class SearchInRotatedArray {
    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] <= nums[mid]) {
                // the left half is normally sorted
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // the right half is normally sorted instead
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

Here's the key thinking, in plain words: even after rotation, at least one half of the array (either the left half or the right half of your current search window) is always still normally sorted. So at every step, first figure out which half is the sorted one, then check if your target could realistically be sitting inside that sorted half. If yes, search there. If no, the target must be in the other, "broken" half, so search there instead.

Tracing the example: left = 0, right = 6, mid = 3, nums[3] = 7, not a match. nums[left] = 4 <= nums[mid] = 7, so the left half is sorted. Is 4 <= 0 < 7? No, since 0 is smaller than 4. So the target must be in the other half: left = 4. Now left = 4, right = 6, mid = 5, nums[5] = 1, not a match. nums[left] = nums[4] = 0 <= nums[mid] = 1, left half sorted. Is 0 <= 0 < 1? Yes. So right = 4. Now left = right = 4, mid = 4, nums[4] = 0 match, return 4.

Time and Space Complexity

• Time: O(log n) even with the rotation, we still cut the search space in half every step.
• Space: O(1)

Any Other Optimal Approach?

You could first find the rotation point with one binary search, then run a second, normal binary search on the correct half this also works and is O(log n), just split into two separate searches instead of one combined one. The single-pass version above is generally preferred in interviews because it shows you can reason about both halves at once, without needing a separate setup step.

Question 5 : Find the Peak Element

A "peak" is an element that is strictly greater than its neighbors. Given an array where no two adjacent elements are equal, find the index of any one peak element. You can assume the array's edges act like negative infinity.

Example:

Input: nums = [1, 2, 3, 1]
Output: 2

Binary Search Code in Java

public class FindPeakElement {
    public static int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[mid + 1]) {
                right = mid; // a peak is at mid or somewhere to its left
            } else {
                left = mid + 1; // a peak must be somewhere to the right
            }
        }

        return left; // left and right have converged onto a peak
    }
}

This one feels a little different from the others, so here's the plain-words version: if the element right after mid is smaller than nums[mid], you're standing on a downward slope, which means a peak exists at mid or somewhere before it so keep searching to the left, including mid itself. If instead the element after mid is bigger, you're standing on an upward slope, so a peak must exist somewhere further to the right and mid itself definitely isn't the answer.

Tracing the example: left = 0, right = 3, mid = 1, nums[1] = 2, nums[2] = 3. Since 2 is not greater than 3, we're on an upward slope, so left = 2. Now left = 2, right = 3, mid = 2, nums[2] = 3, nums[3] = 1. Since 3 > 1, we're on a downward slope, so right = 2. Now left = right = 2, loop ends, return 2 the index of the value 3, which is indeed a peak.

Time and Space Complexity

• Time: O(log n) even though the array itself isn't fully sorted, the "slope direction" at every point behaves predictably enough to safely eliminate half the array each step.
• Space: O(1)

Any Other Optimal Approach?

A simple linear scan checking every element against its neighbors also works and is easy to understand, but it runs in O(n) time. The binary search version above is the optimal approach when the array is large and speed matters, since it consistently beats a linear scan by exploiting the slope pattern instead of checking every element.

Question 6 : Square Root of a Number

Given a non-negative integer x, find and return the integer square root of x meaning the square root rounded down to the nearest whole number, without using any built-in power or square root function.

Example:

Input: x = 28
Output: 5

(Because 5 × 5 = 25, which fits within 28, but 6 × 6 = 36, which is too big.)

Binary Search Code in Java

public class IntegerSquareRoot {
    public static int mySqrt(int x) {
        if (x < 2) {
            return x; // handles 0 and 1 directly, since their square root is themselves
        }
        long left = 1;
        long right = x / 2;
        long result = 1;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            if (square == x) {
                return (int) mid;
            } else if (square < x) {
                result = mid; // this could be our answer, keep it just in case
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return (int) result;
    }
}

This is a great example of Binary Search applied to something that isn't an array at all we're searching through the range of possible answers, from 1 up to x / 2, instead of searching through a list. That range behaves in a sorted, predictable way: if a number's square is too big, every bigger number's square is also too big and if it's small enough, we should keep checking if an even bigger number still fits.

Tracing the example: left = 1, right = 14. mid = 7, 49 > 28, too big, so right = 6. mid = 3, 9 < 28, save result = 3, left = 4. mid = 5, 25 < 28, save result = 5, left = 6. mid = 6, 36 > 28, too big, right = 5. Now left = 6 > right = 5, loop ends, return result = 5 correct.

Time and Space Complexity

• Time: O(log x) we're cutting the range of possible answers in half each time, not the number x itself.
• Space: O(1)

Any Other Optimal Approach?

Newton's Method is a faster numerical approach that can converge on the answer in fewer steps for very large numbers, but it involves floating-point math and is noticeably more complex to implement correctly than this clean binary search version, which is why the binary search approach is usually preferred in interviews.

Question 7 : Binary Search on the Answer (Koko Eating Bananas)

Koko has several piles of bananas and h hours to eat all of them before the zoo guards return. Each hour, she picks one pile and eats up to k bananas from it if the pile has fewer than k bananas, she finishes that pile and stops for the hour, without moving to another pile. Find the minimum integer eating speed k that lets her finish every pile within h hours.

Example:

Input: piles = [3, 6, 7, 11], h = 8
Output: 4

Binary Search Code in Java

public class KokoEatingBananas {
    public static int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int pile : piles) {
            right = Math.max(right, pile); // eating faster than the biggest pile is pointless
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinishInTime(piles, mid, h)) {
                right = mid; // this speed works, maybe a smaller speed also works
            } else {
                left = mid + 1; // too slow, we need to eat faster
            }
        }
        return left;
    }
    private static boolean canFinishInTime(int[] piles, int speed, int h) {
        long hoursNeeded = 0;
        for (int pile : piles) {
            hoursNeeded += (pile + speed - 1) / speed; // ceiling division, no extra Math import needed
        }
        return hoursNeeded <= h;
    }
}

This is, in my experience, the moment Binary Search really "clicks" for a lot of people because there's no array being searched here at all. What's being searched is the space of possible eating speeds, from 1 up to the largest pile. This range has exactly the sorted-like behavior Binary Search needs: if speed 4 is fast enough to finish in time, every speed faster than 4 is also fast enough. If speed 3 is too slow, every speed slower than 3 is also too slow. That one-directional pattern is what makes this searchable with the same halving trick as everything else in this article.

Tracing the example: the biggest pile is 11, so we search speeds from 1 to 11. Checking speed 6 needs 1+1+2+2 = 6 hours, which fits try slower. Checking speed 3 needs 1+2+3+4 = 10 hours, too slow. Checking speed 5 needs 1+2+2+3 = 8 hours, which exactly fits try even slower. Checking speed 4 needs 1+2+2+3 = 8 hours, which also exactly fits. The search converges to left = 4 and no slower speed can finish in time, so 4 is the correct minimum.

Time and Space Complexity

• Time: O(n log m), where n is the number of piles (since we check every pile at every guessed speed) and m is the size of the speed range being searched.
• Space: O(1), aside from the input itself.

Any Other Optimal Approach?

You could try every single speed starting from 1 upward and stop at the first one that works, but that's O(n × maxPile) in the worst case, which is far slower on large pile sizes. Binary searching the answer space, as shown above, is the standard optimal approach for this entire family of "minimum value that satisfies a condition" problems.

1.Does the array have to be sorted for Binary Search to work?

Yes or it needs some equivalent, predictable one-directional structure like a rotated sorted array or a range of possible answers where "if a smaller value works, does a bigger one also work" holds true consistently.

2.What happens if there are duplicate values in the array?

A basic Binary Search will still find a matching index, but it won't guarantee it's the first or last one. For that, you need the boundary-search technique shown in Question 2.

3.Why do we write left + (right - left) / 2 instead of (left + right) / 2?

To avoid integer overflow. If left and right are both extremely large numbers, adding them directly can exceed the maximum value an integer can hold, silently producing a wrong mid value. The safer version avoids this entirely.

4.Can Binary Search be used on something other than an array?

Yes, Question 7 in this article, Koko Eating Bananas, is a great example of using Binary Search on a range of possible answers instead of an array. This "binary search on the answer" pattern is extremely common in interviews once you know to look for it.

5.Is recursive Binary Search better than iterative Binary Search?

Both run in the same O(log n) time. Iterative is usually preferred in interviews because it uses O(1) space, while a recursive version uses a small amount of extra space for each recursive call on the call stack.

6.What's the time complexity of Binary Search and why?

O(log n), because every single comparison eliminates half of the remaining search space. Starting with 1,000,000 items, you'd need only about 20 comparisons to narrow it down to one, since 2 raised to the power of 20 is already just over a million.

7.How is Binary Search different from Linear Search?

Linear Search checks every element one at a time, from start to end and runs in O(n) time. Binary Search requires sorted data but runs dramatically faster, in O(log n) time, by eliminating half the remaining possibilities at every step.

8.Why does my Binary Search loop run forever?

This almost always means the search space isn't actually shrinking usually caused by writing left = mid or right = mid in a spot where it should be mid + 1 or mid - 1. Double-check that every branch of your loop moves left or right strictly closer together.

9.Can I use Binary Search if I don't know the exact size of the search range in advance?

Yes, this comes up sometimes with things like searching an infinite or unknown-length sequence. The usual trick is to first find a rough upper bound by doubling a guess repeatedly (1, 2, 4, 8...) until you've clearly gone too far and then run a normal Binary Search within that discovered range.

10.Is Binary Search always the fastest possible approach?

Not always for extremely small inputs, a simple linear scan can be just as fast in practice due to lower overhead and for certain specialized structures, other techniques like hashing can offer O(1) lookups. But for general sorted-data searching at any real scale, Binary Search is very hard to beat.

How to Identify and Approach Two Pointer Problems?

How to Identify and Approach Sliding Window Patterns in DSA

Graph Traversal (DFS and BFS) Explained with Examples

How to Identify and Approach Backtracking Problems

How to Identify and Approach Dynamic Programming Questions

How to Approach Any DSA Interview Problem: Complete Step-by-Step Guide

Real Interview Experiences: Google, Amazon and Meta

The Ultimate Interview Practice Sheet for FAANG Interviews