Binary Search Algorithm | Iterative & Recursive With Code Examples

19 mins read

Imagine searching for a word in a dictionary. Do you flip through every page one by one? Of course not! You jump to the middle, check the word, and then decide whether to move left or right. That’s precisely how Binary Search works—an efficient searching algorithm that halves the search space with each step.

Used in databases, search engines, and competitive programming, Binary Search is a fundamental algorithm every programmer should master. In this article, we will discuss the binary search algorithm in detail, including how it works, when to use it, its implementation with examples, and its real-world applications.

What Is The Binary Search Algorithm?

Binary search is a divide-and-conquer algorithm used to efficiently find an element in a sorted array. Instead of scanning elements one by one (like in linear search), it repeatedly divides the array into two halves, eliminating half of the search space at every step.

How Binary Search Works

1. Start with a sorted array and two pointers–one at the beginning (low) and one at the end (high).
2. Find the middle element (mid).
3. Compare it with the target:
• If it's equal, you've found the element.
• If it's smaller, the element must be in the right half.
• If it's larger, the element must be in the left half.
4. Repeat the process on the narrowed-down half until the element is found (or the search space is exhausted).

Binary Search Example Walkthrough

Consider searching for 25 in the sorted array:

// Sorted Array
{5, 12, 18, 25, 36, 42, 50}

Here is how binary search will work for this array:

1. Step 1: Middle element = 18 (Too small → Search right half)
2. Step 2: Middle element = 36 (Too big → Search left half)
3. Step 3: Middle element = 25 (Found!)

This efficient approach makes binary search significantly faster than linear search, especially for large datasets.

Conditions For Using Binary Search

Binary search is an efficient algorithm, but it doesn’t work in every scenario. To use it effectively, the following conditions must be met:

1. The Data Must Be Sorted:
   • Binary search relies on order. If the array is unsorted, the algorithm won’t work correctly.
   • Sorting the array beforehand adds extra complexity (O(n log n)), which can negate the benefits of binary search.
2. Random Access is Possible:
   • Binary search frequently jumps to the middle of the array, requiring constant-time access (O(1)) to elements.
   • This is why it works well with arrays but not as efficiently with linked lists, where accessing the middle element takes O(n) time.
3. No Frequent Insertions or Deletions:
   • Dynamic modifications like insertions and deletions require reordering, which disrupts sorting.
   • If data changes frequently, other structures like Balanced Binary Search Trees (BSTs) may be more suitable.
4. The Search Space is Well-Defined:
   • Binary search works best when the target element’s position is predictable (e.g., searching in a sorted database).
   • It’s ineffective in scenarios where relationships between elements are unclear or non-comparable (e.g., unstructured text searches).

With these conditions in mind, let’s move on to how binary search is implemented step by step.

Steps For Implementing Binary Search

Binary search follows a structured approach to efficiently locate an element in a sorted array. Below are the key steps involved in its implementation:

1. Initialize the Search Space: Begin by defining two pointers:
   • low → points to the first element of the array.
   • high → points to the last element of the array.
2. Find the Middle Element: Next we compute the middle index of the array/ data structure:
   • mid=low+high2mid = \frac{low + high}{2}mid=2low+high​
   • Then, access the element at index mid to compare it with the target.
3. Compare and Adjust the Search Space: 
   • If the mid element equals the target, return its index.
   • If the mid element is greater, discard the right half (high = mid - 1).
   • If the mid element is smaller, discard the left half (low = mid + 1).
4. Repeat Until the Search Space is Empty: Continue narrowing down the search space until low exceeds high. If no match is found, return -1 (indicating the element is absent).

Visual Representation Of Binary Search

Say you are working with the following sorted array:
{5, 12, 18, 25, 36, 42, 50}

This is what the binary search would look like if you were looking for 25 (target):

If the target were 30:

Binary search efficiently reduces the number of comparisons, making it O(log n) instead of O(n) like linear search.

Iterative Method For Binary Search With Implementation Examples

The iterative approach to binary search follows a loop-based structure, continuously narrowing the search space until the target is found or the search space is exhausted.

Algorithm Steps:

1. Initialize low = 0 and high = n - 1 (where n is the array size).
2. Run a loop while low <= high:
• Compute mid = (low + high) / 2.
• If arr[mid] == target, return mid.
• If arr[mid] < target, search in the right half (low = mid + 1).
• If arr[mid] > target, search in the left half (high = mid - 1).
3. If the loop ends and the element is not found, return -1.

Iterative Binary Search Program In C++

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int target) {
int low = 0, high = n - 1;

while (low <= high) {
int mid = low + (high - low) / 2; // Avoids integer overflow
if (arr[mid] == target){
return mid; // Element found
}else if (arr[mid] < target){
low = mid + 1; // Search in right half
}else{
high = mid - 1; // Search in left half
}
}

return -1; // Element not found
}

int main() {
int arr[] = {5, 12, 18, 25, 36, 42, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 25;

int result = binarySearch(arr, n, target);

if (result != -1){
cout << "Element found at index " << result << endl;
}else{
cout << "Element not found" << endl;}

return 0;
}

Output:

Element found at index 3

Code Explanation:

We begin the code example by including the header file <iostream> for input and output operations. The using namespace std; statement is added to avoid using std:: before standard library functions.

• Function Definition: We define a C++ function binarySearch() that implements the binary search algorithm iteratively. 
  • The function takes three arguments: arr[] (sorted array), n (array size), and target (element to be searched).
  • Inside, we initialize two pointers: low to 0 (starting index) and high = n - 1 (last index).
• Binary Search Implementation: Then, we use a while loop to repeatedly divide the array into halves as long as low <= high.
• After that, we compare the element at the mid position with the target using an if-else-if statement:
• Inside the loop, we first calculate the middle index. This avoids potential integer overflow that could occur if we used (low + high) / 2.
  • If arr[mid] == target, we return mid (index of the found element).
  • If arr[mid] < target, the target must be in the right half → update low = mid + 1.
  • If arr[mid] > target, the target must be in the left half → update high = mid - 1.
  • If the loop exits without finding the element, -1 is returned, indicating the target was not found.
• Main Execution: In the main() function, we define an integer array arr containing sorted elements {5, 12, 18, 25, 36, 42, 50}.
• Then, we declare and initialize a variable target with the integer data type value 25, which we want to search for.
• We then use the sizeof() operator to calculate the size of the array.
• Next, we call the function binarySearch() function with arr, n, and target as arguments. We store the outcome in the variable result.
• Result Handling: We use an if-else statement to check if the result is not equal to -1, to see whether the element is found:
  • If the result is not -1, the program prints the index of the found element.
  • Otherwise, it prints "Element not found".

Iterative Binary Search Program In Python Example

def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid # Element found
        elif arr[mid] < target:
            low = mid + 1 # Search right half
        else:
            high = mid - 1 # Search left half
    return -1 # Element not found

# Example usage
arr = [5, 12, 18, 25, 36, 42, 50]
target = 25

result = binary_search(arr, target)

if result != -1:
    print(f"Element found at index {result}")
else:
  print("Element not found")

Output:

Element found at index 3

Code Explanation:

In the Python program example below:

• Function Definition: We define a function binary_search() that implements the binary search algorithm iteratively.
  • The function takes two arguments: arr (a sorted list) and target (the element to be searched).
  • Inside the function, we initialize two pointers: low with the value 0 (starting index) and high assigned the value given by len(arr) - 1 (last index).
• Binary Search Implementation: Then, using a while loop, we repeatedly divide the array into halves as long as low <= high.
• Inside the loop, we calculate the middle index (mid = (low + high) // 2) to ensure that integer division avoids errors caused by floating-point values.
• We then compare the element at mid position with the target using an if-elif statement:
  • If arr[mid] == target, we return mid (index of the found element).
  • If arr[mid] < target, the target must be in the right half, so we update low = mid + 1.
  • If arr[mid] > target, the target must be in the left half, so we update high = mid - 1.
  • If the loop exits without finding the element, -1 is returned, indicating the target was not found.
• Main Execution: We define a sorted list arr containing elements [5, 12, 18, 25, 36, 42, 50].
• We also define and initialize a variable target with the valur 25, which we want to search for.
• Then, we call the function binary_search() with arr and target as arguments and store the returned result in result.
• Result Handling: Then, with an if-else statement, we check whether the element is found by comparing the result with -1 (using not equal to relational operator). 
  • If the result is not -1, the program prints the index of the found element.
  • Otherw ise, it prints "Element not found".

Recursive Method For Binary Search

Unlike the iterative approach, the recursive method breaks the problem into smaller subproblems by making repeated function calls until the base condition is met.

Algorithm Steps:

1. Base Case: If low > high, return -1 (element not found).
2. Compute mid = (low + high) / 2.
3. Compare arr[mid] with the target:
• If arr[mid] == target, return mid.
• If arr[mid] < target, recursively search in the right half (low = mid + 1).
• If arr[mid] > target, recursively search in the left half (high = mid - 1).

Recursive Binary Search Program In C++

#include <iostream>
using namespace std;

int binarySearch(int arr[], int low, int high, int target) {
if (low > high) {
return -1; // Element not found
}

int mid = low + (high - low) / 2; // Avoid integer overflow
if (arr[mid] == target) {
return mid; // Element found
} else if (arr[mid] < target) {
return binarySearch(arr, mid + 1, high, target); // Search right half
} else {
return binarySearch(arr, low, mid - 1, target); // Search left half
}
}

int main() {
int arr[] = {5, 12, 18, 25, 36, 42, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 25;

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

if (result != -1) {
cout << "Element found at index " << result << endl;
} else {
cout << "Element not found" << endl;
}

return 0;
}

Output:

Element found at index 3

Code Explanation:

• Function Definition: We define a function binarySearch() that implements the recursive version of the binary search algorithm. The function takes four arguments:
  • arr[]: The sorted array in which we search for the target.
  • low: The starting index of the array (or subarray).
  • high: The last index of the array (or subarray).
  • target: The element to be searched.
• Recursive Binary Search Implementation: We define the base case, where the function first checks if low > high. This means that the element is not present in the array or subarray. In this case, -1 is returned.
• The middle index is calculated in the same way as in the iterative version:
  • If arr[mid] == target, the function returns mid, indicating that the element has been found.
  • If arr[mid] < target, we know the target lies in the right half, so the function is called recursively with updated low = mid + 1 and the same high.
  • If arr[mid] > target, the target lies in the left half, so the function is called recursively with updated high = mid - 1 and the same low.
  • If the target element is not found during the recursion, the function eventually returns -1.
• Main Execution: We define the sorted array arr containing elements {5, 12, 18, 25, 36, 42, 50}. The target is set to 25.
• We call the function binarySearch() with arr, 0, n - 1, and target. The returned result is stored in the result variable.
• Result Handling: We check if the result is not equal to -1 using an if-else statement.
  • If the result is not -1, the program prints the index of the found element.
  • Otherwise, it prints "Element not found".

Recursive Binary Search Program In Python

def binary_search(arr, low, high, target):
    if low > high:
        return -1 # Element not found    

    mid = (low + high) // 2
    if arr[mid] == target:
        return mid # Element found
    elif arr[mid] < target:
        return binary_search(arr, mid + 1, high, target) # Search right half
    else:
        return binary_search(arr, low, mid - 1, target) # Search left half

# Example usage
arr = [5, 12, 18, 25, 36, 42, 50]
target = 25

result = binary_search(arr, 0, len(arr) - 1, target)

if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found")

Output:

Element found at index 3

Code Explanation:

• Function Definition: We define a function binary_search() that implements the recursive binary search algorithm. The function takes four arguments:
  • arr: The sorted list in which we search for the target.
  • low: The starting index of the list (or sublist).
  • high: The last index of the list (or sublist).
  • target: The element to be searched.
• Recursive Binary Search Implementation: We define the base case where the function checks if low > high. If true, it returns -1, indicating the element is not present.
• The middle index is calculated in the same way as the iterative approach:
  • If arr[mid] == target, the function returns mid, indicating the element has been found.
  • If arr[mid] < target, we recursively search the right half by calling the function with updated low = mid + 1 and the same high.
  • If arr[mid] > target, we recursively search the left half by calling the function with updated high = mid - 1 and the same low.
  • If the element is not found, the function will eventually return -1.
• Main Execution: We define the sorted list arr containing elements [5, 12, 18, 25, 36, 42, 50]. The target is set to 25.
• We call the function binary_search() with arr, 0, len(arr) - 1, and target. The result is stored in the result.
• Result Handling: We check if the result is not -1 using an if-else statement.
  • If the result is not -1, it prints the index of the found element.
  • Otherwise, it prints "Element not found".

Complexity Analysis Of Binary Search Algorithm

In this section, we will explore the time complexity and space complexity of the binary search algorithm, providing insights into its efficiency in different scenarios.

Time Complexity Of Binary Search Algorithm

• Best Case: In the best-case scenario, the element is found at the middle index on the first comparison, so the algorithm terminates immediately. This occurs in constant time.
  Time Complexity (Best Case): O(1)
• Average and Worst Case: In both the average and worst cases, we halve the search space at each step. This is because, with each iteration (or recursion), we discard half of the remaining elements. In the worst case, we may have to repeatedly halve the list until we narrow down to the target or determine the target is absent.
  Time Complexity (Average and Worst Case): O(log n)

Binary search is highly efficient with a time complexity of O(log n), making it much faster than linear search for large datasets.

Space Complexity Of Binary Search Algorithm

• Iterative Approach: The iterative approach of binary search uses a fixed amount of space. It only requires a few variables to track the indices (low, high, mid), irrespective of the size of the input.
  Space Complexity (Iterative): O(1)
• Recursive Approach: The recursive approach involves function calls, and each recursive call adds a new frame to the call stack. The maximum depth of recursion is proportional to the logarithm of the array size, which happens when the array is repeatedly halved.
  Space Complexity (Recursive): O(log n)

Summary Of Complexity Analysis For Binary Search Algorithm

Iterative Vs. Recursive Implementation Of Binary Search

We’ve already seen the implementation examples of the two approaches to binary search– iterative and recursive. In this section, we will briefly discuss the key differences and advantages of each approach to binary search.

Iterative Approach:

• In this approach, the binary search works using a while loop that repeatedly divides the array in half. This method is preferred when minimizing memory usage is a priority, as it doesn't involve extra function calls.
• The space complexity for the iterative approach is O(1), since it only uses a few variables to track the indices (low, high, mid).

Recursive Approach:

• In this approach, binary search is implemented using function calls that call themselves with a narrowed search space. This method is usually easier to understand and implement as it follows a more natural divide-and-conquer pattern.
• The space complexity for the recursive approach is O(log n), due to the function calls stacked on the call stack.

Key Differences Iterative Vs. Recursive Binary Search

Advantages & Disadvantages Of Binary Search

Binary search is a highly efficient algorithm when applied to sorted arrays. However, like any algorithm, it comes with its own set of advantages and limitations. The table below highlights the pros and cons of binary search in data structures.

Binary search is a great algorithm for searching in sorted arrays, offering fast search times and efficiency for large datasets. However, it has its limitations, particularly requiring a sorted array and being unsuitable for linked lists or very small datasets.

Practical Applications & Real-World Examples Of Binary Search

Binary search is not just a theoretical concept—it has significant real-world applications across various domains. From searching in large datasets to optimizing pricing algorithms, binary search is used extensively to solve practical problems efficiently.

• Searching in Sorted Arrays: Binary search is commonly used to search for an element in sorted arrays. The array could be part of any system that requires fast access to sorted data, like a dictionary, inventory, or ordered list. Example Use Case: Finding the position of a word in a sorted dictionary or looking up a specific product in a sorted inventory list.
• Finding Elements in Large Data Sets: When working with massive datasets (like logs, databases, or large collections of files), binary search helps locate the desired element in logarithmic time rather than linearly scanning the entire set. This makes it extremely efficient in big data scenarios. Example Use Case: Searching for a customer’s order in a massive e-commerce database or locating a document in a large index of files.
• Applications in Databases: In databases, especially when performing search queries on sorted tables, binary search is essential for improving query performance. Many database systems rely on indexing techniques that use binary search to quickly find records without scanning the entire dataset. Example Use Case: When running an SQL query with a WHERE clause on a sorted column, the database may internally use binary search on an index to find the rows more efficiently.

Real-World Examples Of Binary Search

1. Version Control Systems: Version control systems like Git use binary search to pinpoint which commit introduced a bug. By searching through the commit history in a binary fashion, developers can quickly isolate the problematic commit.
2. Pricing Algorithms: Binary search is used in competitive pricing algorithms where a company adjusts its prices based on competitor data. By maintaining a sorted list of competitor prices, binary search can quickly identify the optimal pricing point.
3. Stock Market Algorithms: In high-frequency trading, sorted price lists are used for real-time decision-making. Binary search enables traders to quickly retrieve the best bid/ask price, maximizing trading efficiency.

Conclusion

Binary search is a powerful and efficient algorithm widely used in various fields, from searching in sorted arrays to optimizing large datasets. By reducing the search space logarithmically with each step, it drastically improves search time, making it ideal for large-scale systems and real-time applications.

Despite its advantages, binary search has its limitations–most notably, the requirement for a sorted array and its unsuitability for linked lists. However, when these conditions are met, binary search offers significant performance gains over linear search and is often the go-to algorithm in situations that demand quick lookups. Understanding binary search will undoubtedly improve the efficiency of your systems and make your searches faster.

Frequently Asked Questions

Q1. What is the time complexity of binary search?

The time complexity of binary search is O(log n), where n is the number of elements in the array. This is because, at each step, the algorithm halves the search space, making the number of comparisons logarithmic with respect to the size of the input.

Q2. Can binary search be used on unsorted arrays?

No, binary search only works on sorted arrays. If the array is unsorted, the algorithm cannot efficiently divide the search space. In such cases, other search methods like linear search are more appropriate.

Q3. How is binary search implemented recursively and iteratively?

Binary search can be implemented in two ways:

• Iteratively: Using a loop to repeatedly divide the search range.
• Recursively: By calling the same function on smaller subarrays until the target is found or the search space is exhausted.

Both approaches have the same time complexity (O(log n)), but the iterative version typically uses less memory because it avoids the overhead of recursive function calls.

Q4. Is binary search only for searching in arrays?

While binary search is most commonly used in sorted arrays, it can also be adapted for other data structures like binary search trees (BSTs), sorted linked lists, and even files or databases. The key requirement is that the data must be in sorted order.

Q5. What are the disadvantages of binary search?

• Requires sorted data: The data needs to be sorted before applying binary search, which can be a drawback if the data is constantly changing.
• Not efficient for linked lists: Binary search requires random access to elements, so it's inefficient on linked lists since they don't allow for direct indexing.

Enjoyed reading this? Do check the following out:

1. What Is Linear Data Structure? Types, Uses & More (+ Examples)
2. Single Linked List In Data Structure | All Operations (+Examples)
3. DSA Cheatsheet Unlocked: Roadmap, Boot Camp & Must-Know Resources
4. Graph Data Structure | Types, Algorithms & More (+Code Examples)
5. Advantages And Disadvantages Of Linked Lists Summed Up For You
6. 53 Frequently Asked Linked List Interview Questions With Answers 2025