Binary Search Made Easy

Learning Objectives

By the end of this article, you should be able to:

• explain Binary Search in your own words
• understand why Binary Search requires sorted data
• use low, high, and mid correctly
• trace Binary Search manually
• write Binary Search in C#
• explain why Binary Search has O(log n) time complexity
• compare Binary Search with Linear Search
• identify situations where Binary Search should and should not be used
• recognize Binary Search ideas in real applications and algorithm problems

2.1 Introduction

Have you ever searched for something and realized that checking everything one by one would take too long?

Imagine looking for a word in a dictionary. Would you open the first page and start reading every word until you found it?

Probably not.

You would open somewhere near the middle, look at the words, and decide whether you should move to the left or the right.

Without realizing it, you are already thinking like a programmer.

Computers also need to search for things: a player ID, a product, a student record, a score, a username, or a number inside a large collection.

Sometimes there may be only ten items. Sometimes there may be one million. If we check every item one by one, the answer can take a lot of work to find.

So today we are going to learn a smarter question:

Instead of checking the next item, can we remove half of the possible answers?

That question leads us to Binary Search.

But before we talk about algorithms and code, I want to tell you a story.

2.2 Ali and the Pizza

Ali had one serious problem. He was hungry. Not normal hungry. The kind of hungry where even the delivery app starts looking beautiful. So Ali ordered a large pizza with 16 slices

When the pizza arrived, he opened the box, smiled proudly, and said:

“Finally. Sixteen slices. All mine.”

Ali picked up the first slice. Then someone knocked on the door. His friend entered, looked at the pizza, and said:

“Bro… pizza?”

Ali looked at his friend. Then at the pizza. Then back at his friend. After a few painful seconds, Ali decided to share half.

His pizza became: 16 → 8

Ali still had eight slices. He smiled again.

“Eight is enough.”

Then the door opened again. Two more friends appeared.

One of them said:

“Wow! Perfect timing.”

Ali did not think the timing was perfect. But again, he shared.

8 → 4

Now Ali had four slices. He quickly picked one up before anyone else could arrive. Knock, knock. Ali froze. Another group of friends walked in.

They looked at the pizza. Ali looked at the door and wondered why he had so many friends.

After another round of sharing:

4 → 2

Now only two slices remained. Ali held them close.

“These are mine. No more sharing.”

Then his best friend walked into the room. He smiled and asked:

“You wouldn’t let your best friend stay hungry, would you?”

Ali looked at the two slices. He looked at his friend. He looked back at the slices.

Finally:

2 → 1

Ali sat quietly with one lonely slice.

A few minutes earlier, he had:

16 slices

Now he had:

1 slice

Ali asked:

“Can someone explain how sixteen slices became one so quickly?”

His programmer friend picked up a marker and wrote:

16 → 8 → 4 → 2 → 1

“Look,” he said. “Every time you shared, the amount became half.”

Then he counted:

16 → 8 = Step 1

8 → 4 = Step 2

4 → 2 = Step 3

2 → 1 = Step 4

“Only four steps.”

Ali looked at him.

“I lost fifteen slices, and you are excited about the steps?”

His friend laughed.

“Because you just demonstrated one of the most important ideas behind Binary Search.”

Ali stared at him.

“I ordered pizza. How did programming enter my house?”

That is a fair question.

But Ali’s pizza has just given us an important idea:

When we repeatedly cut something in half, a large amount can become very small in only a few steps.

Ali’s pizza changed like this:

16 → 8 → 4 → 2 → 1

Later in this article, Binary Search will do something very similar.

It will not divide pizza. It will divide the search area. And instead of asking:

“Who ate my pizza?”

we will ask:

“Which half of the search area can we remove?”

That small idea will turn out to be one of the smartest ways to search.

2.3 Connection With Logarithms

In the previous article, Logarithms Made Easy for Algorithms, we studied repeated halving.

16 → 8 → 4 → 2 → 1

Because four halving steps are required, we can write:

log₂(16) = 4

This chapter uses the same idea. However, instead of reducing pizza slices, Binary Search reduces:

possible answers

For example:

16 possibilities → 8 → 4 → 2 → 1

This repeated halving is the mathematical reason Binary Search is so efficient.

Prerequisite Note: If logarithms and repeated halving are still unclear, review the previous article, Logarithms Made Easy for Algorithms before continuing. Understanding that idea will make Binary Search much easier.

2.4 Discovering Binary Search

Before learning the formal definition, let us discover the algorithm ourselves.

Imagine a teacher says:

“I am thinking of a number between 1 and 100.”

Your job is to find the secret number.

One student begins:

“Is it 1?”

No.

“2?”

No.

“3?”

No.

This method will eventually work.

But suppose the secret number is:

97

The student may need a very large number of guesses.

So we need a smarter strategy.

Instead of asking:

“Which number should I check next?”

ask:

“Which guess can remove the largest number of wrong possibilities?”

That question leads us directly to Binary Search.

2.5 Start From the Middle

The middle of the range 1 to 100 is approximately:

50

So we guess:

50

Suppose the teacher says:

“The secret number is greater than 50.”

Now think carefully.

Do we still need to consider:

1, 2, 3, … 49?

No.

They are impossible.

With only one comparison, we removed almost half of the possible answers.

Our search area changed from:

1–100

to:

51–100

Now we check the middle again.

Suppose we choose:

75

The teacher says:

“Too high.”

Now we can remove the upper half.

Again, our search area becomes much smaller.

The pattern is:

Check the middle → Compare → Remove half → Repeat

Without writing any code, we have discovered the main idea behind Binary Search.

figure : range 1–100, first guess 50, then half of the range removed, followed by another middle guess.

2.6 What Is Binary Search?

Now the formal definition should make sense.

Binary Search is a searching algorithm that finds a target in sorted data by checking the middle element and repeatedly removing the half that cannot contain the target.

The algorithm follows three main actions:

1. Check the middle.
2. Compare the middle value with the target.
3. Remove the half that cannot contain the target.

Then repeat.

A simple memory pattern is:

Middle → Compare → Remove Half → Repeat

2.7 Why Is It Called Binary Search?

The word binary is related to two.

At each step, the search area is divided into two parts:

Left Half | Right Half

After checking the middle, Binary Search decides which half may still contain the target. One half is kept. The other half is removed. The process continues until the target is found or no search area remains.

2.8 Why Must the Data Be Sorted?

This is one of the most important rules of Binary Search.

Consider the following array:

[2, 5, 8, 13, 20, 31, 45]

The array is sorted. Suppose we want to find: 31

The middle value is: 13

Since: 31 > 13

and the array is sorted, we know that 31 cannot be inside:

[2, 5, 8, 13]

Therefore, we can remove that entire section. The remaining search area becomes:

[20, 31, 45]

Now consider an unsorted array:

[20, 5, 45, 2, 31, 8, 13]

Suppose the middle value is: 2

Our target is still: 31

Although 31 > 2

we cannot safely remove the left side.

Why?

Because larger values may appear anywhere.

Therefore:

Sorted order allows Binary Search to decide which half can safely be removed.

Figure: one sorted row where half can be removed, and one unsorted row where the target could appear anywhere.

2.9 From Human Thinking to Computer Thinking

Humans can say:

“Search the right half.”

A computer needs exact positions.

It needs to know:

• where the current search begins
• where the current search ends
• which position is in the middle

For this purpose, Binary Search commonly uses three variables:

low high mid

2.10 Understanding low

low represents:

the first index of the current search area

Consider:

[2, 5, 8, 13, 20, 31, 45]

The indexes are:

0, 1, 2, 3, 4, 5, 6

Get Mujeeb Ur Rehman’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

At the beginning, the search starts at index:

0

So:

low = 0

A simple memory rule is:

low = start

2.11 Understanding high

high represents:

the last index of the current search area

The last index in our array is:

6

So:

high = 6

Memory rule:

high = end

At the beginning:

low = 0

high = 6

This means:

Search everything from index 0 to index 6.

2.12 Understanding mid

mid represents the middle position of the current search area.

We calculate it using:

int mid = low + (high - low) / 2;

At the beginning:

low = 0

high = 6

Therefore:

mid = 3

The value at index 3 is:

13

Memory rule:

mid = check here

2.13 Worked Example: Find 31

Consider:

[2, 5, 8, 13, 20, 31, 45]

Target: 31

Step 1

Start with:

low = 0

high = 6

Calculate:

mid = 3

The value at index 3 is: 13

Compare: 31 > 13

Therefore, the target must be on the right side. We remove the left half.

Update:

low = mid + 1

So: low = 4

Step 2

Now: low = 4 and high = 6

The current search area is: [20, 31, 45]

Calculate the new middle: mid = 5

The value at index 5 is: 31

Compare: 31 == 31

The target is found.

Result:

31 is located at index 5.

Figure: showing the full array, the middle value 13, removal of the left half, and then 31 being found.

2.14 The Three Possible Cases

After checking the middle element, only three things can happen.

Case 1: Target Equals Middle

If:

target == numbers[mid]

the target has been found.

Case 2: Target Is Greater

If:

target > numbers[mid]

search the right half.

Update:

low = mid + 1;

Case 3: Target Is Smaller

If:

target < numbers[mid]

search the left half.

Update:

high = mid - 1;

A useful memory rule is:

Equal → Found
Bigger → Right
Smaller → Left

2.15 Explain the Algorithm Before Writing Code

Before writing Binary Search in C#, try to explain it in ordinary language.

A good explanation is:

Start with the whole sorted collection. Check the middle element. If the target is greater, remove the left half. If the target is smaller, remove the right half. If the middle value equals the target, stop. Repeat until the target is found or no elements remain.

If you understand that paragraph, the code will be much easier. If you cannot explain it yet, return to the worked example before continuing.

Programming Principle: Understand the idea first. Code it second.

2.16 Binary Search Algorithm

The algorithm can now be written as simple steps:

1. Set low to the first index.
2. Set high to the last index.
3. While low <= high:

• calculate mid
• compare numbers[mid] with the target
• if equal, return mid
• if the target is greater, move low
• if the target is smaller, move high

4. If no search area remains, return -1.

2.17 Binary Search in C#

In this article, I’ll use C# to implement Binary Search, but the algorithm itself is language-independent. You can follow the same logic in Python, Java, C++, JavaScript, or any other programming language.

static int BinarySearch(int[] numbers, int target) 
{ 
 int low = 0; // start index

 int high = numbers.Length - 1; // end index 

 while (low <= high)
 {
// midle index between low and end with the formula 
  int mid = low + (high - low) / 2; 

  if (numbers[mid] == target) //Did we find the target?
      { 
        // if yes match found return mid value
        return mid; 
      } 

   if (numbers[mid] < target) //The target is bigger, so search right.
      { 
        low = mid + 1;
      } 
   else
      { 
         high = mid - 1;  //The target is smaller, so search left.
      } 
   }
  return -1; // If the target does not exist:
}

2.18 Why Binary Search Is Fast

Suppose we have:

1,000,000 sorted items

Linear Search may need to inspect almost every item. Binary Search reduces the search area approximately like this:

1,000,000

↓

500,000

↓

250,000

↓

125,000

↓

62,500

↓

31,250

↓

15,625

↓

…

↓

1

Only about 20 halving steps are required. This is why Binary Search is extremely efficient for large sorted collections.

2.19 Why Binary Search Is O(log n)

Binary Search has a time complexity of O(log n) because it removes about half of the remaining search area at every step. We will explore time complexity and O(log n) in much more detail in the next article; for now, just remember that repeated halving makes Binary Search very fast.

2.20 Linear Search vs Binary Search

Linear Search and Binary Search solve a similar problem but think very differently.

Linear Search asks:

“Is this item the target?”

If not, it moves to the next item.

Binary Search asks:

“Which entire half can I prove does not contain the target?”

Consider 1,000,000 items:

Search Method Approximate Worst-Case ComparisonsTime ComplexityLinear Search1,000,000O(n)Binary Search: About 20O(log n)

Binary Search is fast not because the computer performs comparisons faster.

It is fast because it performs far fewer comparisons.

2.21 Where Binary Search Can Be Used

Binary Search can be useful whenever data is ordered, and comparisons allow us to remove large parts of the search area.

In the next article, we will take these examples one by one and see how Binary Search can be applied to real problems such as

• sorted player IDs
• student roll numbers
• product IDs
• timestamps
• dictionary words
• ranking tables
• game scores
• XP thresholds
• insertion positions
• finding ranges
• finding boundaries

2.22 When Should Binary Search Be Used?

Binary Search is a good choice when:

• the data is sorted
• the collection is large
• fast lookup is useful
• searching happens repeatedly
• one comparison allows a large part of the search space to be removed

A useful question is:

After one comparison, can I safely eliminate a large part of the remaining possibilities?

If the answer is yes, Binary Search may be appropriate.

2.23 When Should Binary Search NOT Be Used?

Binary Search should not normally be used directly when:

• the data is unsorted
• you cannot determine which half is safe to remove
• the collection is extremely small
• sorting the collection would cost more than the search is worth
• the data structure does not allow efficient access to middle elements

A good programmer does not try to use Binary Search everywhere.

A good programmer asks:

Does Binary Search fit this problem?

2.24 Common Beginner Mistakes

Mistake 1: Using Binary Search on Unsorted Data

Standard Binary Search relies on order.

Without sorted data, the comparison with the middle does not tell us which side can safely be removed.

Mistake 2: Writing

low = mid;

instead of:

low = mid + 1;

The middle element has already been checked.

If we keep it inside the next search range, the algorithm may get stuck checking the same position.

Mistake 3: Writing

high = mid;

instead of:

high = mid - 1;

Again, the old middle has already been checked.

Mistake 4: Forgetting the Last Remaining Element

For this implementation, use:

while (low <= high)

The equality matters because:

low == high

means exactly one valid element still remains to be checked.

2.30 Check Your Understanding

Before moving on, answer these questions in your own words:

1. What does Binary Search check first?
2. Why does the data need to be sorted?
3. What does low represent?
4. What does high represent?
5. What does mid represent?
6. What happens when the target is greater than the middle value?
7. What happens when the target is smaller than the middle value?
8. What does -1 mean in our implementation?
9. Why does Binary Search have O(log n) complexity?
10. What is the main difference between Linear Search and Binary Search?

If you can explain these answers without memorizing sentences, you understand the algorithm.