Introduction
Searching is one of the most common operations in computer programming. Whether you’re looking for a contact in your phone, searching for a student in a database, or finding a product on an e-commerce website, an efficient searching algorithm can significantly improve performance.
In the previous blog, we explored Linear Search, which checks every element one by one. While Linear Search is simple and works well for small datasets, it becomes slow as the size of the data grows.
This is where Binary Search comes into the picture.
Binary Search is one of the fastest searching algorithms for sorted arrays. Instead of checking every element, it repeatedly divides the search space into two halves, making it extremely efficient for large datasets.
In this article, you’ll learn:
- What Binary Search is
- Why it is faster than Linear Search
- The prerequisite for using Binary Search
- How Binary Search works
- Step-by-step dry runs
- Binary Search algorithm
- Iterative Java implementation
- Time and Space Complexity
- Advantages and Disadvantages
- Common mistakes beginners make
Let’s begin!
What is Binary Search?
Binary Search is a searching algorithm that searches an element in a sorted array by repeatedly dividing the search interval into half.
Instead of checking every element one by one, Binary Search compares the target with the middle element.
- If the target is equal to the middle element, the search is complete.
- If the target is smaller, continue searching in the left half.
- If the target is greater, continue searching in the right half.
This process continues until the element is found or the search interval becomes empty.
Prerequisite: The Array Must Be Sorted
Binary Search only works correctly on sorted data.
Consider this sorted array:
10 20 30 40 50 60 70 80 90
Searching for 70 is straightforward because we know:
- Numbers on the left are smaller.
- Numbers on the right are larger.
Now consider an unsorted array:
40 10 70 20 90 30 80
If we choose the middle element here, we cannot decide which half contains the target.
Therefore,
Binary Search requires the data to be sorted before searching.
Why is Binary Search Faster?
Suppose you have a dictionary containing 1000 words.
Would you start checking from the first page?
Of course not!
You usually open the dictionary somewhere near the middle.
- If your word comes before that page, you search the left half.
- Otherwise, you search the right half.
Every time, half of the dictionary is ignored.
Binary Search works exactly the same way.
Instead of checking every element, it keeps eliminating half of the remaining elements.
Real-Life Examples
Example 1: Dictionary
You open approximately in the middle.
If the word comes before the middle page, you ignore the remaining half.
Example 2: Telephone Directory
Rather than checking names one after another, you jump to the middle section.
Example 3: Guess the Number Game
Suppose your friend asks you to guess a number between 1 and 100.
You ask:
“Is it 50?”
If the answer is Higher, you immediately ignore numbers 1–50.
If the answer is Lower, you ignore numbers 51–100.
Every guess cuts the search space into half.
This is Binary Search.
How Binary Search Works
Consider the sorted array:
Index : 0 1 2 3 4 5 6 7 8
Value :10 20 30 40 50 60 70 80 90
Search for 70.
Initially
Low = 0
High = 8
Calculate middle
mid = (0 + 8) / 2
mid = 4
Middle element
50
Since
70 > 50
Ignore the left half.
New search range
60 70 80 90
Now
Low = 5
High = 8
Calculate middle
mid = (5 + 8) / 2
mid = 6
Middle element
70
Found!
Only 2 comparisons were required.
Visual Representation
Initial Array
10 20 30 40 [50] 60 70 80 90
Target is larger.
Ignore
10 20 30 40 50
Remaining
60 [70] 80 90
Found.
Another Dry Run
Search 20
10 20 30 40 50 60 70 80 90
Step 1
Middle
50
Since
20 < 50
Ignore the right half.
Remaining
10 20 30 40
Step 2
Middle
20
Found.
Dry Run When Element Does Not Exist
Search
65
Array
10 20 30 40 50 60 70 80 90
Step 1
Middle = 50
Search right.
Step 2
Middle = 70
Search left.
Step 3
Middle = 60
Search right.
Now
Low > High
Search ends.
Result
Element Not Found
Binary Search Algorithm
- Set low = 0
- Set high = n − 1
- Find middle element.
- Compare middle with target.
- If equal, return index.
- If target is smaller, search left half.
- If target is greater, search right half.
- Repeat until low becomes greater than high.
- If not found, return -1.
Formula to Calculate Middle
The simplest formula is:
mid = (low + high) / 2;
However, in very large arrays, adding low + high can overflow the integer range.
A safer approach is:
mid = low + (high - low) / 2;
This produces the same result while avoiding overflow.
Java Program (Iterative Binary Search)
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {10,20,30,40,50,60,70,80,90};
int target = 70;
int low = 0;
int high = arr.length - 1;
int position = -1;
while(low <= high) {
int mid = low + (high - low) / 2;
if(arr[mid] == target) {
position = mid;
break;
}
else if(target < arr[mid]) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
if(position != -1)
System.out.println("Element Found at Index " + position);
else
System.out.println("Element Not Found");
}
}
Output
Element Found at Index 6
Program Explanation
Creating the Array
int[] arr = {10,20,30,40,50,60,70,80,90};
A sorted integer array is created.
Target Element
int target = 70;
The value we want to search.
Initial Search Range
int low = 0;
int high = arr.length - 1;
Initially, the entire array is considered.
Loop
while(low <= high)
Continue searching as long as the search range exists.
Calculating Middle
int mid = low + (high - low) / 2;
Find the middle index.
Element Found
if(arr[mid] == target)
Store the index and terminate.
Search Left Half
high = mid - 1;
Used when
target < arr[mid]
Search Right Half
low = mid + 1;
Used when
target > arr[mid]
Dry Run of the Program
Array
10 20 30 40 50 60 70 80 90
Search = 70
| Iteration | Low | High | Mid | Element | Action |
|---|---|---|---|---|---|
| 1 | 0 | 8 | 4 | 50 | Search Right |
| 2 | 5 | 8 | 6 | 70 | Found |
Only 2 iterations are needed.
Another Example
Search = 10
| Iteration | Low | High | Mid | Element | Action |
|---|---|---|---|---|---|
| 1 | 0 | 8 | 4 | 50 | Left Half |
| 2 | 0 | 3 | 1 | 20 | Left Half |
| 3 | 0 | 0 | 0 | 10 | Found |
Time Complexity Analysis
Binary Search is highly efficient because it reduces the search space by half after every comparison.
Suppose an array contains 16 elements.
16 → 8 → 4 → 2 → 1
Only 5 comparisons are needed in the worst case.
If the array has 1024 elements:
1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1
Only 10 comparisons are required.
This is why Binary Search is much faster than Linear Search for large datasets.
Best Case
The target element is exactly at the middle.
Example:
10 20 30 40 [50] 60 70
Only one comparison is required.
Time Complexity: O(1)
Average Case
The element is found after repeatedly dividing the search space.
Time Complexity: O(log n)
Worst Case
The element is the last one examined or is not present in the array.
Time Complexity: O(log n)
Space Complexity
The iterative Binary Search algorithm uses only a few variables:
lowhighmidposition
No additional array or data structure is created.
Space Complexity: O(1)
Advantages of Binary Search
- Extremely fast for large datasets.
- Reduces the search space by half after each comparison.
- Requires only constant extra memory in its iterative form.
- Efficient for repeated searches on sorted data.
- Widely used in databases, search engines, and standard libraries.
Disadvantages of Binary Search
- Works only on sorted data.
- If the data is unsorted, it must first be sorted, which takes additional time.
- More difficult to understand than Linear Search for beginners.
- Not suitable for linked lists because random access is inefficient.
Binary Search vs Linear Search
| Feature | Linear Search | Binary Search |
|---|---|---|
| Data Requirement | Sorted or Unsorted | Sorted Only |
| Searching Method | Sequential | Divide and Conquer |
| Best Case | O(1) | O(1) |
| Average Case | O(n) | O(log n) |
| Worst Case | O(n) | O(log n) |
| Implementation | Very Easy | Moderate |
| Suitable for Large Data | No | Yes |
Common Mistakes Beginners Make
1. Using Binary Search on an Unsorted Array
This is the most common mistake.
40 10 80 20 70
Binary Search will not produce correct results.
2. Incorrect Loop Condition
Incorrect:
while(low < high)
Correct:
while(low <= high)
Using < may skip checking the last remaining element.
3. Incorrect Middle Calculation
Although
mid = (low + high) / 2;
works for small arrays, the safer version is:
mid = low + (high - low) / 2;
4. Updating the Wrong Boundary
When searching the left half:
high = mid - 1;
When searching the right half:
low = mid + 1;
Using incorrect updates may lead to an infinite loop.
Interview Questions
1. What is Binary Search?
A searching algorithm that repeatedly divides a sorted search space into two halves until the target element is found or the search interval becomes empty.
2. What is the prerequisite for Binary Search?
The array or list must be sorted.
3. What is the worst-case time complexity?
O(log n)
4. What is the best-case time complexity?
O(1)
5. What is the space complexity of iterative Binary Search?
O(1)
6. Why is Binary Search faster than Linear Search?
Because it eliminates half of the remaining elements after every comparison instead of checking every element one by one.
Practice Programs
Try solving these on your own:
- Search a number entered by the user.
- Search an element in a sorted array.
- Search a character in a sorted character array.
- Search a word in a sorted array of strings.
- Count the number of iterations taken to find an element.
- Modify the program to return
-1when the element is not found.
Summary
Binary Search is one of the most efficient searching algorithms for sorted data. By repeatedly dividing the search space into two halves, it significantly reduces the number of comparisons needed to locate an element. While it requires the data to be sorted beforehand, its logarithmic time complexity O(log n) makes it an excellent choice for searching large datasets. Understanding the iterative approach, the role of the low, high, and mid pointers, and the importance of maintaining a sorted array provides a strong foundation for solving more advanced searching problems.
In the next part of this series, we’ll explore Recursive Binary Search, finding the first and last occurrence of an element, handling duplicate values, searching in strings, advanced interview questions, and several real-world Binary Search problems frequently asked in coding interviews.
