Binary search explained simply for beginners with examples, Java code, time complexity, mistakes, interview patterns, and practical DSA tips.

Binary Search Explained Simply: A Beginner's Guide

If you had to find one number inside a list containing one million sorted numbers, would you really check every number one by one?

You could, but there is a much smarter approach. Instead of checking every element, you can look at the middle, decide which half could contain the answer, and immediately ignore the other half.

This is the basic idea behind Binary Search.

Binary Search can look intimidating when you first see code with left, right, and middle. But the actual idea is surprisingly simple: keep cutting the search space in half until you find the target or there is nothing left to search.

In this guide, we will understand Binary Search from the ground up, using a simple analogy, a step-by-step array example, Java code, complexity analysis, common mistakes, interview patterns, and practical problems.

What Is Binary Search?

Binary Search is a searching algorithm that repeatedly divides a sorted search space into two halves.

In simple words, instead of checking every element from the beginning, Binary Search asks:

“Can I eliminate half of the possibilities right now?”

The basic process is:

1. Find the middle element.
2. Compare the middle element with the target.
3. If they are equal, you found the target.
4. If the target is greater, ignore the left half.
5. If the target is smaller, ignore the right half.
6. Repeat the same process with the remaining half.

That is Binary Search.

The important requirement is that the search space must have an order that allows you to safely eliminate one side. In the most common beginner example, that means the array is sorted.

A Simple Real-World Example

Imagine you are looking for the word "Mango" in a dictionary.

Would you start from the first page and read every word until you reach Mango?

Probably not.

You would open the dictionary somewhere near the middle. Suppose you see words starting with R.

You immediately know Mango comes before R, so you can ignore roughly half of the dictionary.

Now you look somewhere in the middle of the remaining pages. Suppose you see F.

Mango comes after F, so you ignore the earlier half of what remains.

You keep doing this until you find Mango.

This is exactly the intuition behind Binary Search.

The Important Idea

Suppose you have 1000 possible pages.

1. Check the middle → roughly 500 possibilities remain.
2. Check the middle again → roughly 250 remain.
3. Again → roughly 125 remain.
4. Again → roughly 62 remain.
5. Continue until the search space becomes tiny.

You are not checking every possibility. You are repeatedly eliminating half of the possibilities.

Binary Search With a Simple Array Example

Let's use this sorted array:

[10, 20, 30, 40, 50, 60, 70, 80, 90]

Our target is:

70

Each element has an index:

Index:  0   1   2   3   4   5   6   7   8
Value: 10  20  30  40  50  60  70  80  90

We use three important variables:

• left: the beginning of the current search space
• right: the end of the current search space
• middle: the middle index between left and right

Step 1: Start With the Whole Array

left = 0
right = 8

Calculate the middle:

middle = 4

The value at index 4 is:

arr[4] = 50

Our target is 70.

Since:

70 > 50

the target must be somewhere to the right of 50.

So we can safely ignore:

[10, 20, 30, 40, 50]

Our new search space is:

[60, 70, 80, 90]

Step 2: Search the Remaining Half

Now:

left = 5
right = 8

The middle index is:

middle = 6

And:

arr[6] = 70

Our target is also 70.

Therefore:

arr[middle] == target

We found the target at index 6.

What Just Happened?

We started with 9 elements.

After checking one middle element, we eliminated half of the search space.

Then we checked the middle of what remained and found the answer.

That is the power of Binary Search.

Why Does Binary Search Need a Sorted Array?

This is one of the most important concepts to understand.

Binary Search works because the order of the data tells us which half we can eliminate.

Consider this sorted array:

[10, 20, 30, 40, 70, 90]

Suppose the target is 70.

The middle value is 30 or 40 depending on how you calculate the middle. If the middle value is smaller than 70, you know that the target must be to the right because the array is sorted.

Now consider an unsorted array:

[10, 70, 20, 90, 40, 30]

Suppose you look at the middle element and see 90.

Can you safely say that 70 is on the left?

No.

Because the remaining values have no useful ordering. The target could be on either side.

So the key requirement is not simply "Binary Search likes sorted arrays."

The real reason is:

You need an ordered search space so that comparing the middle tells you which side can be eliminated.

Some advanced Binary Search problems do not involve a visibly sorted array. Instead, the possible answers have a monotonic property: once a condition changes from false to true, or true to false, it stays that way. This is called Binary Search on the answer, and we will briefly cover it later.

Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Requirement	No sorting required	Usually requires sorted or monotonic search space
Approach	Check elements one by one	Repeatedly divide the search space
Worst-case time	O(n)	O(log n)
Beginner difficulty	Easier	Slightly more complex
Best use case	Small or unsorted data	Sorted or ordered data

Suppose you have 1,000,000 sorted numbers and need to find one number.

With Linear Search, you may need to check a very large number of elements.

With Binary Search, each comparison removes about half of the remaining possibilities.

However, Binary Search is not always better. If the data is unsorted, Linear Search may be the straightforward choice. For a tiny collection, the simplicity of Linear Search may also be perfectly reasonable.

Binary Search Algorithm Step by Step

Now let's turn the idea into an algorithm.

Step 1: Set Left

left = 0

The first element has index 0.

Step 2: Set Right

right = n - 1

If the array contains n elements, the last index is n - 1.

Step 3: Find the Middle

middle = left + (right - left) / 2

You may also see:

middle = (left + right) / 2

Both give the same middle index when the values are within a safe integer range. However, left + (right - left) / 2 is commonly preferred because it avoids a potential integer overflow when left + right becomes too large.

For a beginner, the main thing to remember is that this calculates the middle index safely.

Step 4: Compare the Middle With the Target

There are three possibilities.

Case 1: Middle equals target

arr[middle] == target

You found the target, so return the index.

Case 2: Middle is smaller than target

arr[middle] < target

The target must be on the right side, so:

left = middle + 1

Case 3: Middle is greater than target

arr[middle] > target

The target must be on the left side, so:

right = middle - 1

Step 5: Repeat

Continue while:

left <= right

When:

left > right

there is no search space left. That means the target does not exist in the array.

Binary Search Code in Java

Here is a beginner-friendly iterative implementation:

public class BinarySearch {

    public static int binarySearch(int[] arr, int target) {

        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {

            int middle = left + (right - left) / 2;

            if (arr[middle] == target) {
                return middle;
            }

            if (arr[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {

        int[] arr = {10, 20, 30, 40, 50, 60, 70, 80, 90};
        int target = 70;

        int result = binarySearch(arr, target);

        System.out.println("Index: " + result);
    }
}

The output is:

Index: 6

Understanding the Code

1. Create the left pointer:

int left = 0;

The search starts at the first index.

2. Create the right pointer:

int right = arr.length - 1;

The search initially ends at the last index.

3. Continue while a search space exists:

while (left <= right)

As long as left has not moved beyond right, there are still elements to examine.

4. Calculate the middle:

int middle = left + (right - left) / 2;

This gives us the middle index of the current search space.

5. Check whether we found the target:

if (arr[middle] == target) {
    return middle;
}

If the middle value equals the target, return its index.

6. Search the right half:

if (arr[middle] < target) {
    left = middle + 1;
}

If the middle value is smaller than the target, everything at or before the middle can be ignored.

7. Search the left half:

else {
    right = middle - 1;
}

If the middle value is larger than the target, everything at or after the middle can be ignored.

8. Target not found:

return -1;

Returning -1 is a common convention for saying that the target does not exist in the array.

What Happens If the Target Is Not Found?

Suppose our array is:

[10, 20, 30, 40, 50, 60, 70]

and the target is:

45

Binary Search keeps eliminating halves.

Eventually, there will be no valid elements left to examine.

That means:

left > right

At that point, the loop ends and the method returns:

-1

So Binary Search does not keep searching forever. The pointers eventually cross when the target is absent.

Binary Search Using Recursion

Binary Search can also be implemented using recursion. Recursion means a function calls itself with a smaller version of the problem.

For Binary Search, each recursive call works on only one half of the current search space.

A recursive solution needs a base case. If the search space becomes invalid, the target is not present.

public class RecursiveBinarySearch {

    public static int binarySearch(
            int[] arr, int left, int right, int target) {

        if (left > right) {
            return -1;
        }

        int middle = left + (right - left) / 2;

        if (arr[middle] == target) {
            return middle;
        }

        if (arr[middle] < target) {
            return binarySearch(arr, middle + 1, right, target);
        }

        return binarySearch(arr, left, middle - 1, target);
    }

    public static void main(String[] args) {

        int[] arr = {10, 20, 30, 40, 50, 60, 70};
        int target = 50;

        int result = binarySearch(
                arr, 0, arr.length - 1, target);

        System.out.println("Index: " + result);
    }
}

The logic is the same as the iterative version:

• If the search space is empty, return -1.
• If the middle value is the target, return the index.
• If the target is greater, recursively search the right half.
• If the target is smaller, recursively search the left half.

For beginners, it is usually easier to understand the iterative version first. Once the pointer logic is clear, recursion becomes easier to understand.

Both versions take O(log n) time. The iterative version uses O(1) auxiliary space, while the recursive version uses O(log n) call-stack space because of the recursive calls.

Time and Space Complexity of Binary Search

Time Complexity

The best-case time complexity is:

O(1)

This happens when the target is exactly the middle element during the first comparison.

The average and worst-case time complexity is:

O(log n)

Why?

Because the search space is roughly divided by two after every comparison.

Imagine you have 1,000,000 elements. You do not need to inspect all one million elements. You repeatedly cut the remaining possibilities in half until the search space becomes very small.

This is why Binary Search scales much better than checking every element one by one when the data is appropriately ordered.

Space Complexity

For the iterative implementation:

O(1)

Only a few variables such as left, right, and middle are used.

For the recursive implementation:

O(log n)

The additional space comes from the recursive call stack.

Common Binary Search Mistakes Beginners Make

1. Using Binary Search on Unsorted Data

Problem: You cannot safely decide which half to eliminate if the values are not ordered.

Fix: Confirm that the search space is sorted or has a valid monotonic property.

2. Updating the Pointers Incorrectly

After checking the middle, use:

left = middle + 1

or:

right = middle - 1

Do not leave the middle inside the search space when you have already determined that it is not the answer. Otherwise, you can create an infinite loop.

3. Forgetting the Loop Condition

A common iterative condition is:

while (left <= right)

If left becomes greater than right, there is nothing left to search.

4. Creating an Infinite Loop

If neither left nor right moves after a comparison, the same middle element may be checked repeatedly.

Make sure your updates actually reduce the search space.

5. Incorrect Middle Calculation

Prefer:

int middle = left + (right - left) / 2;

It avoids potential integer overflow associated with directly adding two large indexes.

6. Returning the Wrong Index

Remember that middle is an index, while arr[middle] is the value stored at that index.

Confusing these two is a very common beginner mistake.

7. Confusing Index With Value

If:

arr[6] = 70

then 6 is the index and 70 is the value.

8. Not Handling the Target-Not-Found Case

Your algorithm should clearly define what happens when the target does not exist. Returning -1 is a common approach when returning an index.

9. Using the Wrong Boundary Conditions

Binary Search has several valid boundary conventions, especially for advanced variations. Beginners should first master the standard inclusive approach:

left = 0
right = n - 1
while (left <= right)

10. Memorizing the Code Without Understanding It

This is perhaps the biggest mistake.

If you only memorize a Binary Search template, a small change in the problem can make the solution confusing.

Instead, remember the core question:

Which half can I safely eliminate?

The Most Important Binary Search Pattern

Do not think:

"Where is the target?"

Think:

"Which half can I safely eliminate?"

This mental shift is extremely important.

Binary Search is fundamentally about reducing the search space.

The search space simply means the part of the data where the answer could still exist.

At the beginning, the search space might be the entire array.

After one comparison, it becomes roughly half.

After another comparison, it becomes roughly half again.

Once you learn to see problems in terms of a shrinking search space, many Binary Search problems become easier to recognize.

How to Recognize a Binary Search Problem

When reading a coding problem, look for these clues:

• The data is sorted.
• The search space is ordered.
• You need to find a value efficiently.
• The problem asks whether a certain condition is possible.
• The possible answers follow a monotonic pattern.
• You need to find a minimum or maximum value that satisfies a condition.

What Does "Monotonic" Mean?

For Binary Search on the answer, you may not have a sorted array. Instead, you may have possible answers that behave in an ordered way.

Imagine a problem asks:

Find the minimum speed needed to finish a task within 10 hours.

Suppose speed 5 is too slow, speed 6 is too slow, and speed 7 is fast enough.

Once you reach a speed that is fast enough, higher speeds will also be fast enough.

The possibilities may look like:

Too slow  Too slow  Too slow  Fast enough  Fast enough  Fast enough
    5         6         7          8             9          10

There is a clear transition from one state to another. Binary Search can sometimes find that transition efficiently.

This is known as Binary Search on the answer. It is an important advanced pattern, but beginners should first become comfortable with standard Binary Search.

Common Binary Search Variations

First Occurrence

If an array contains duplicate values, you may need to find the first position where the target appears rather than stopping at any occurrence.

Last Occurrence

This is similar, but you continue searching after finding the target to locate its final occurrence.

Lower Bound

Lower bound problems generally ask for the first position where a value is greater than or equal to a target.

Upper Bound

Upper bound problems generally ask for the first position where a value is greater than a target.

Search in a Rotated Sorted Array

The array was originally sorted but has been rotated. You use Binary Search while determining which portion remains sorted.

Finding a Peak Element

You may use Binary Search-like reasoning to find a position where the element satisfies a peak condition, even though the problem is not simply searching for a specific value.

Binary Search on Answer

Instead of searching for an element, you search through possible answers and use a feasibility check to determine which half can be eliminated.

These variations are useful for interviews, but master standard Binary Search first.

How to Practice Binary Search

Do not immediately jump into difficult Binary Search problems. Build your understanding progressively.

Level 1: Basic Search

• Find a target in a sorted array.
• Handle a target that does not exist.
• Search a single-element array.
• Search when the target is at the beginning.
• Search when the target is at the end.

Level 2: Boundary Problems

• First occurrence
• Last occurrence
• Lower bound
• Upper bound

Level 3: Pattern Problems

• Search in a rotated sorted array
• Find a peak element
• Search in variations of ordered data

Level 4: Binary Search on Answer

• Minimum feasible value
• Maximum feasible value
• Capacity problems
• Speed problems
• Distance or allocation problems

The goal is not to memorize dozens of solutions. The goal is to recognize why Binary Search works in each problem.

Binary Search Interview Tips

Knowing the code is only one part of a coding interview. You should also be able to explain your reasoning.

A good structure is:

1. Explain the straightforward or brute-force approach.
2. Explain why it may be inefficient.
3. Identify that the data or search space is sorted or monotonic.
4. Explain how Binary Search reduces the search space.
5. Describe the pointer movement.
6. Write the code.
7. Explain time and space complexity.
8. Test important edge cases.

Important Edge Cases

• Empty array
• One-element array
• Target at the beginning
• Target at the end
• Target not present
• Duplicate values
• Very large input

For example, if the interviewer gives you a sorted array, do not immediately start coding. First explain why the sorted property allows you to eliminate half of the search space.

That demonstrates understanding rather than memorization.

Frequently Asked Questions

What is Binary Search in simple terms?

Binary Search finds a target by repeatedly checking the middle of a sorted or otherwise ordered search space and eliminating the half that cannot contain the answer.

Why does Binary Search require a sorted array?

Sorting lets you determine which side of the middle can contain the target. Without that ordering, you usually cannot safely eliminate half of the data.

Is Binary Search faster than Linear Search?

For a sufficiently large sorted search space, Binary Search can be much faster because it takes O(log n) time in the average and worst case, compared with O(n) for Linear Search. But Linear Search can be more appropriate for unsorted or very small data.

What is the time complexity of Binary Search?

The best case is O(1), while the average and worst case are O(log n).

Can Binary Search work on an unsorted array?

Standard Binary Search cannot safely search an arbitrary unsorted array because the middle value does not tell you which half can be eliminated. Some advanced problems use Binary Search on a different kind of ordered or monotonic search space.

What is the difference between iterative and recursive Binary Search?

Both use the same basic logic. The iterative version uses a loop and O(1) auxiliary space, while the recursive version uses function calls and O(log n) call-stack space.

When should I use Binary Search?

Look for sorted or ordered data, or a search space where a yes/no condition changes monotonically. These properties allow you to eliminate half of the possibilities at each step.

What is Binary Search on the answer?

It is a technique where you Binary Search over possible answers instead of directly searching an array. It works when you can efficiently check whether a candidate answer is feasible and feasibility changes monotonically.

Is Binary Search important for coding interviews?

Yes, Binary Search is an important DSA concept and appears in many coding-problem patterns. However, no single algorithm is guaranteed to appear in every interview. Its relevance depends on the role and hiring process.

How should a beginner practice Binary Search?

Start with standard Binary Search on sorted arrays, then practice first and last occurrence, lower and upper bounds, rotated arrays, and finally Binary Search on the answer.

Final Takeaway

If Binary Search felt confusing before, remember just one idea:

Binary Search repeatedly cuts the search space in half.

Start with a sorted array. Keep two boundaries: left and right. Find the middle. Compare the middle value with the target. Then eliminate the half that cannot contain the answer.

The basic pattern is:

if middle == target
    found

else if middle < target
    search right half

else
    search left half

Once this logic becomes natural, the Java code becomes much easier to understand.

Do not rush into advanced variations. First become comfortable with the standard algorithm, pointer movement, edge cases, and the reason sorting makes Binary Search possible. Then move toward first and last occurrence, rotated arrays, and Binary Search on the answer.

The most important lesson is not memorizing a piece of code. It is learning to recognize when you can safely eliminate half of a search space.

Once you can see that pattern, Binary Search stops being a confusing DSA topic and becomes one of the most useful problem-solving techniques in your toolkit.