Introduction
In Part 1, we learned the fundamentals of Binary Search, including:
- What Binary Search is
- Why the array must be sorted
- How Binary Search works
- Dry run examples
- Iterative Java implementation
- Time and Space Complexity
- Advantages and Disadvantages
In this article, we’ll move to more advanced Binary Search concepts that are frequently asked in technical interviews and competitive programming.
By the end of this article, you’ll know how to:
- Implement Recursive Binary Search
- Search in arrays of Strings
- Find the First Occurrence of an element
- Find the Last Occurrence of an element
- Count duplicate occurrences
- Find the Insertion Position
- Find the Floor and Ceiling of a number
- Solve common interview problems
- Avoid common Binary Search mistakes
Let’s begin!
Recursive Binary Search
Instead of using a loop, Binary Search can also be implemented using recursion.
A recursive function repeatedly calls itself while reducing the search range.
The recursive approach follows the same logic as the iterative version.
- Find the middle element.
- Compare it with the target.
- Search the left half or right half.
- Stop when the element is found or when
low > high.
Recursive Algorithm
BinarySearch(arr, low, high, target)
If low > high
return -1
Find middle
If middle element == target
return middle
If target < middle element
Search left half
Else
Search right half
Recursive Java Program
public class RecursiveBinarySearch {
static int binarySearch(int[] arr, int low, int high, int target) {
if (low > high)
return -1;
int mid = low + (high - low) / 2;
if (arr[mid] == target)
return mid;
if (target < arr[mid])
return binarySearch(arr, low, mid - 1, target);
return binarySearch(arr, mid + 1, high, target);
}
public static void main(String[] args) {
int[] arr = {10,20,30,40,50,60,70,80};
int result = binarySearch(arr,0,arr.length-1,60);
if(result!=-1)
System.out.println("Found at Index " + result);
else
System.out.println("Element Not Found");
}
}
Output
Found at Index 5
Dry Run of Recursive Binary Search
Array
10 20 30 40 50 60 70 80
Search = 60
First Call
low = 0
high = 7
mid = 3
Element = 40
Search right half.
Second Call
low = 4
high = 7
mid = 5
Element = 60
Found!
Iterative vs Recursive Binary Search
| Feature | Iterative | Recursive |
|---|---|---|
| Uses Loop | Yes | No |
| Uses Recursion | No | Yes |
| Space Complexity | O(1) | O(log n) |
| Easy to Debug | Yes | Moderate |
| Interview Usage | Very Common | Also Common |
Although both approaches have the same time complexity, the iterative version is generally preferred because it does not consume additional stack memory.
Binary Search on Strings
Binary Search works on strings as long as they are sorted alphabetically.
Example:
Apple
Banana
Cherry
Grapes
Mango
Orange
Java Program
public class BinarySearchString {
public static void main(String[] args) {
String[] fruits = {
"Apple",
"Banana",
"Cherry",
"Grapes",
"Mango",
"Orange"
};
String target = "Mango";
int low = 0;
int high = fruits.length - 1;
while(low <= high){
int mid = low + (high-low)/2;
int result = fruits[mid].compareTo(target);
if(result == 0){
System.out.println("Found at Index " + mid);
return;
}
if(result > 0)
high = mid - 1;
else
low = mid + 1;
}
System.out.println("Not Found");
}
}
Output
Found at Index 4
Finding the First Occurrence
Consider this sorted array:
10 20 20 20 30 40 50
Searching for 20.
A normal Binary Search may return 1, 2, or 3.
Suppose we specifically need the first occurrence.
The idea is simple:
- When you find the element, store its index.
- Continue searching toward the left.
Java Program
public class FirstOccurrence {
public static void main(String[] args) {
int[] arr = {10,20,20,20,30,40};
int target = 20;
int low = 0;
int high = arr.length - 1;
int answer = -1;
while(low <= high){
int mid = low + (high-low)/2;
if(arr[mid] == target){
answer = mid;
high = mid - 1;
}
else if(target < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
System.out.println(answer);
}
}
Output
1
Finding the Last Occurrence
The logic is almost identical.
When the target is found:
- Store the answer.
- Continue searching toward the right.
answer = mid;
low = mid + 1;
Example
10 20 20 20 30 40
Output
3
Counting Total Occurrences
Once you know:
- First Occurrence
- Last Occurrence
The total count becomes:
Count = Last Index − First Index + 1
Example
10 20 20 20 30 40
First
1
Last
3
Count
3 - 1 + 1
= 3
Finding the Insertion Position
Suppose
10 20 30 40 60
Insert
50
The correct position is
Index = 4
This problem is commonly asked in coding interviews.
The answer is simply the value of low after Binary Search completes.
Java Program
public class InsertPosition {
public static void main(String[] args) {
int[] arr = {10,20,30,40,60};
int target = 50;
int low = 0;
int high = arr.length-1;
while(low <= high){
int mid = low + (high-low)/2;
if(arr[mid] == target){
System.out.println(mid);
return;
}
if(target < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
System.out.println("Insert at Index " + low);
}
}
Output
Insert at Index 4
Finding the Floor of a Number
The Floor is the largest value that is less than or equal to the target.
Example
10 20 30 40 50
Target
35
Floor
30
Finding the Ceiling of a Number
The Ceiling is the smallest value that is greater than or equal to the target.
Example
10 20 30 40 50
Target
35
Ceiling
40
These are common interview questions because they demonstrate a strong understanding of Binary Search boundaries.
Binary Search in Real Applications
Binary Search is used in:
- Database indexing
- Search engines
- Dictionary applications
- Library management systems
- Student information systems
- Contact search
- Operating systems
- Version control systems
- Game development
- AI decision trees
Common Mistakes
1. Forgetting to Sort the Array
Binary Search only works correctly on sorted data.
2. Incorrect Mid Calculation
Avoid
mid = (low + high)/2;
Prefer
mid = low + (high-low)/2;
3. Infinite Loop
Wrong updates
high = mid;
low = mid;
Correct updates
high = mid - 1;
low = mid + 1;
4. Wrong Loop Condition
Incorrect
while(low < high)
Correct
while(low <= high)
Binary Search vs Linear Search
| Feature | Linear Search | Binary Search |
|---|---|---|
| Sorted Array Required | No | Yes |
| Best Case | O(1) | O(1) |
| Average Case | O(n) | O(log n) |
| Worst Case | O(n) | O(log n) |
| Large Data Performance | Slow | Fast |
| Implementation Difficulty | Easy | Moderate |
Interview Questions
1. Why must the array be sorted?
Binary Search relies on the ordering of elements to decide which half of the array can be discarded. Without sorting, that decision would be incorrect.
2. What is Divide and Conquer?
Binary Search follows the Divide and Conquer strategy by repeatedly dividing the search space into two halves until the answer is found or the search interval becomes empty.
3. Which is better: Iterative or Recursive Binary Search?
Both have the same time complexity of O(log n).
However, the iterative version is generally preferred because it uses O(1) extra space, while the recursive version uses the call stack, requiring O(log n) space.
4. What happens if the element is not present?
The search continues until low > high. At that point, the algorithm returns -1, indicating that the element does not exist in the array.
5. What is the maximum number of comparisons?
For an array of size n, the maximum number of comparisons is proportional to log₂(n), giving Binary Search a worst-case time complexity of O(log n).
Practice Programs
Try implementing the following programs on your own:
- Recursive Binary Search
- Binary Search using user input
- Search in a sorted array of strings
- Find the first occurrence of an element
- Find the last occurrence of an element
- Count duplicate occurrences
- Find the insertion position
- Find the floor of a number
- Find the ceiling of a number
- Compare the number of iterations taken by Linear Search and Binary Search for the same dataset.
Summary
Binary Search is one of the most efficient searching algorithms available for sorted data. By repeatedly dividing the search space into two halves, it dramatically reduces the number of comparisons required, making it ideal for large datasets. In this article, you explored recursive Binary Search, searching strings, finding the first and last occurrence of duplicate elements, counting occurrences, determining insertion positions, and understanding the concepts of floor and ceiling. These variations are among the most frequently asked Binary Search problems in coding interviews and competitive programming.
Together, Part 1 and Part 2 provide a complete understanding of Binary Search—from the fundamentals to advanced interview-oriented techniques. Mastering these concepts will prepare you for more advanced topics such as Jump Search, Interpolation Search, and Binary Search on Answer, all of which build upon the principles you’ve learned here.
