Binary search

March 18, 2025 binary-search algorithm data-structures searching sorting

In computer science, binary search, also known as half-interval search,logarithmic search,or binary chop,is a search algorithm that finds the position of a target value within a sorted array.

Binary Search Algorithm – Iterative and Recursive Implementation

The Binary Search Algorithm is a way to find a specific item in a sorted list quickly. Instead of checking each item one by one, it works by repeatedly cutting the list in half. If the item you’re looking for is in the first half, it ignores the second half, and vice versa. This process keeps narrowing down the search until the item is found. Because it halves the list each time, it’s very efficient and works in O(logn) time, which is much faster than checking every item.

Real World Analogy (Searching for a Page in a Book):

Binary Search Explained with a Book Example (Searching for a Page) Imagine you have a large book and you want to find a particular page (say page 450) quickly. Instead of flipping through one page at a time (linear search), you can use binary search to find it much faster

Steps to Find Page 450 Using Binary Search:

Step 1: Open the Middle Page

Suppose the book has 1000 pages.
Open the middle page: Page 500.

Step 2: Compare the Page Number

If Page 500 is greater than 450 → The target page is in the left half (pages 1–499).
If Page 500 is less than 450 → The target page is in the right half (pages 501–1000).
If Page 500 is exactly 450, we found it! 🎉

Step 3: Repeat in the Correct Half

Since 450 is less than 500, we now search only in pages 1 to 499.
Again, pick the middle page: Page 250.
Since 450 is greater than 250, we search in pages 251 to 499.

Step 4: Keep Narrowing Down

Middle of 251–499 → Page 375. (450 is greater, so search 376–499)
Middle of 376–499 → Page 437. (450 is greater, so search 438–499)
Middle of 438–499 → Page 468. (450 is smaller, so search 438–467)
Middle of 438–467 → Page 452. (450 is smaller, so search 438–451)
Middle of 438–451 → Page 449. (450 is greater, so search 450–451)
Middle of 450–451 → Page 450! Found it! ✅

What is Binary Search Algorithm?

Binary search is an efficient method for finding a specific value in a sorted list. Instead of scanning each element one by one, it speeds up the process by repeatedly cutting the search space in half. The search begins by identifying the middle element of the list. If this middle element matches the target value, the search is complete. However, if the target is smaller than the middle element, the search continues in the left half of the list. Conversely, if the target is larger, the search shifts to the right half. This process repeats until the target is found or the search space becomes empty. By reducing the number of elements to check at each step, binary search is significantly faster than a linear search, making it ideal for large datasets

The Binary Search Algorithm is a quick way to find a number in a sorted list by repeatedly cutting the search space in half.

Interactive Example:

Target:

Click 'Start Search' to begin

Low Index

Mid Index

High Index

How Binary Search Works

Start with a sorted array.
Set low to the first index (0) and high to the last index (length-1).
Calculate the middle index: mid = Math.floor((low + high) / 2).
If the middle element equals the target, we found it!
If the middle element is less than the target, search the right half (low = mid + 1).
If the middle element is greater than the target, search the left half (high = mid - 1).
Repeat steps 3-6 until the element is found or low > high (element not in array).

Implementation (Iterative Approach):

java

cpp

python

public class BinarySearch {
    public static int binarySearch(int[] array, int target) {
        int start = 0;
        int end = array.length - 1;

        // Repeat until the search space is exhausted
        while (start <= end) {
            int middle = start + (end - start) / 2;

            // If middle element is the target, return its index
            if (array[middle] == target) {
                return middle;
            }
            // If target is smaller, search in the left half
            else if (array[middle] > target) {
                end = middle - 1;
            }
            // If target is larger, search in the right half
            else {
                start = middle + 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};  // <--- this is our search space
        int target = 30;                   // <--- this is our target element
        System.out.println("Index of " + target + ": " + binarySearch(arr, target));
    }
}

#include <iostream>
using namespace std;

// Function to perform binary search
int binarySearch(int array[], int size, int target) {
    int start = 0, end = size - 1;

    // Repeat until the search space is exhausted
    while (start <= end) {
        int middle = start + (end - start) / 2;  // Prevent overflow

        // If middle element is the target, return its index
        if (array[middle] == target) {
            return middle;
        }
        // If target is smaller, search in the left half
        else if (array[middle] > target) {
            end = middle - 1;
        }
        // If target is larger, search in the right half
        else {
            start = middle + 1;
        }
    }

    return -1;  // Target not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 30;

    cout << "Index of " << target << ": " << binarySearch(arr, size, target) << endl;
    return 0;
}

# Function to perform binary search
def binary_search(array, target):
    start, end = 0, len(array) - 1

    # Repeat until the search space is exhausted
    while start <= end:
        middle = start + (end - start) // 2  # Prevent overflow

        # If middle element is the target, return its index
        if array[middle] == target:
            return middle
        # If target is smaller, search in the left half
        elif array[middle] > target:
            end = middle - 1
        # If target is larger, search in the right half
        else:
            start = middle + 1

    return -1  # Target not found

if __name__ == '__main__':
    arr = [10, 20, 30, 40, 50]  # <- this is our search space
    target = 30                 # <- this is our target value
    print(f"Index of {target}: {binary_search(arr, target)}")

Binary Search Algorithm (Recursive Approach)

Given a sorted array A of n elements and a target value T, we find the index of T using recursion.

Steps:

Define the recursive function
- The function takes A, T, start, and end as inputs.
- If start > end, that means the element is not present, so return -1.
Find the middle element
- Calculate mid = start + (end - start) / 2 to avoid integer overflow.
Compare the middle element with the target
- If A[mid] == T, return mid because we found the element.
- If A[mid] > T, that means the element is in the left half, so call the function again with end = mid - 1:
```
return binarySearch(A, T, start, mid - 1);
```
- If A[mid] < T, the element must be in the right half, so call the function with start = mid + 1:
```
return binarySearch(A, T, mid + 1, end);
```
Recursion continues
- The function keeps calling itself with smaller and smaller parts of the array.
- Either we find the target, or we reach the base case (start > end), which means the element is not in the array.
Final answer
- If found, return mid.
- Otherwise, return -1 to indicate that the target is missing.

Implementation (Recursive Approach):

java

cpp

python

public class BinarySearchRecursive {
    public static int binarySearch(int[] array, int target, int start, int end) {
        if (start > end) return -1; // Base case: not found

        int middle = start + (end - start) / 2; // Prevent overflow

        if (array[middle] == target) return middle; // Found
        else if (array[middle] > target) return binarySearch(array, target, start, middle - 1); // Left half
        else return binarySearch(array, target, middle + 1, end); // Right half
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        int target = 30;
        int index = binarySearch(arr, target, 0, arr.length - 1);
        System.out.println("Index of " + target + ": " + index);
    }
}

#include <iostream>
using namespace std;

int binarySearch(int array[], int target, int start, int end) {
    if (start > end) return -1; // Base case: not found

    int middle = start + (end - start) / 2; // Prevent overflow

    if (array[middle] == target) return middle; // Found
    else if (array[middle] > target) return binarySearch(array, target, start, middle - 1); // Left half
    else return binarySearch(array, target, middle + 1, end); // Right half
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int target = 30;
    int size = sizeof(arr) / sizeof(arr[0]);

    int index = binarySearch(arr, target, 0, size - 1);
    cout << "Index of " << target << ": " << index << endl;
    return 0;
}

def binary_search(array, target, start, end):
    if start > end:
        return -1  # Base case: not found

    middle = start + (end - start) // 2  # Prevent overflow

    if array[middle] == target:
        return middle  # Found
    elif array[middle] > target:
        return binary_search(array, target, start, middle - 1)  # Left half
    else:
        return binary_search(array, target, middle + 1, end)  # Right half

if __name__ == '__main__':
    arr = [10, 20, 30, 40, 50]
    target = 30

    index = binary_search(arr, target, 0, len(arr) - 1)
    print(f"Index of {target}: {index}")

Iterative vs Recursive Binary Search

Approach	Implementation	Space Complexity	Time Complexity
Iterative	Uses a `while` loop to narrow the search range	O(1) (constant extra space)	O(log n)
Recursive	Calls itself with updated `S` and `E`	O(log n) (due to recursive stack)	O(log n)

Key Differences:

The iterative approach is more space-efficient since it avoids recursive function calls.
The recursive approach is easier to understand but consumes extra space due to recursion.
Both approaches have the same O(log n) time complexity.

Why do we use `mid = s + (e - s) / 2` in C++?

In Python, we can use mid = s + (e - s) // 2 to prevent overflow.
However, in C++, the range of int is -2^31 to 2^31 - 1.
If we calculate mid = (s + e) / 2, it may cause integer overflow for large values of s and e.
To prevent this, we use the formula:

Execute The code below to see the difference between the two methods
# [                          (x-1)       x          ]
#                            2^31 - 2   2^31 - 1
s = 2**31 - 2
e = 2**31 - 1

print("int max: ", 2**31 - 1)               # -> 2147483647
print("normal way: ", s + e / 2)            # -> 3221225469.5
print("modified way: ", s + (e - s) / 2)    # -> 2147483646.5

Roadmap to Master Binary Search:

References

https://en.wikipedia.org/wiki/Binary_search

Binary search

Binary Search Algorithm – Iterative and Recursive Implementation

Real World Analogy (Searching for a Page in a Book):

What is Binary Search Algorithm?

Interactive Example:

How Binary Search Works

Here’s how it works step by step: 1. Find the `middle element` of the list. 2. Compare it

Implementation (Iterative Approach):

Binary Search Algorithm (Recursive Approach)

Steps:

Implementation (Recursive Approach):

Iterative vs Recursive Binary Search

Key Differences:

Why do we use `mid = s + (e - s) / 2` in C++?

Roadmap to Master Binary Search:

References

Similar Posts

Binary search

Binary Search Algorithm – Iterative and Recursive Implementation

Real World Analogy (Searching for a Page in a Book):

What is Binary Search Algorithm?

Interactive Example:

How Binary Search Works

Here’s how it works step by step: 1. Find the middle element of the list. 2. Compare it

Implementation (Iterative Approach):

Binary Search Algorithm (Recursive Approach)

Steps:

Implementation (Recursive Approach):

Iterative vs Recursive Binary Search

Key Differences:

Why do we use mid = s + (e - s) / 2 in C++?

Roadmap to Master Binary Search:

References

Similar Posts

Here’s how it works step by step: 1. Find the `middle element` of the list. 2. Compare it

Why do we use `mid = s + (e - s) / 2` in C++?