Skip to main content

Binary Search

Binary Search Algorithm Solution: Iterative & Recursive Ways

Binary Search Algorithm Solution

Problem Description:

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.

Examples:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums,, and its index is 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums, so return -1

Constraints:

  • 1 <= nums.length <= 10⁴
  • -10⁴ < nums[i], target < 10⁴
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Basic Approach to solve the problem:

Alright, let’s start with the most basic approach we can use to solve this problem.

We are given an array nums and need to determine if a number, target, is present in the array. If it is, we return its index; if not, we return -1.

The simplest solution nums first element and compare each element with the target.

If we find a match, we return its index. If we reach the end of the array without finding the target, we simply return -1.

Sounds easy, right?

This method is known as linear search because we linearly go through the array, one element at a time. For an array of size n, this approach would require up to n comparisons in the worst case, where the target is not present or is located at the very end of the array.

What is linear search?

Linear search is the simplest searching algorithm where we traverse the array element by element, starting from the first index, and compare each element with the target value. If a match is found, we return the index of the element; otherwise, we continue until the end of the array.

linearSearch(nums, target):

    // traverse the entire array nums
    for i = 0 to length(nums) - 1:
    
        // compare each element with target
        if nums[i] == target:
        
            // return index of element if equal to target
            return i
    
    // return -1 if target not found
    return -1

This method's time complexity is O(n) since we might need to check all n elements in the array.

However, we are asked to solve this problem in O(log n) time, which is much faster. So, while linear search is straightforward, we need to explore a better and more efficient approach to meet the problem's requirements.

Let's see how we can optimize it:

We are given an array of integers and a number called the target. Our task is to find whether the target is present in the array and, if so, return its index.

To do this, one common approach that we saw previously is to traverse the entire array, and whenever we find the target, we return its index. However, this approach takes O(n) time complexity, and the question asks us to solve it in O(log n) time complexity.

Alright, here’s something interesting to observe—our array is sorted.

Now let me ask you a quick question:
Is it easier to find a number in a sorted array or in an unsorted array? The obvious answer is that it’s easier in a sorted array.

But why is that?

In a sorted array, the elements are arranged in increasing order, which means if we pick any element, we can immediately tell whether the number we’re looking for will be to the left (smaller numbers) or the right (larger numbers). This gives us a clear direction to search in, allowing us to eliminate large portions of the array in one step. In contrast, we don’t have this advantage in an unsorted array—we have to check each element one by one because there’s no order or pattern to follow.

Binary Search Algorithm Solution

Now, coming to our problem, since the array is sorted, if we pick any number in the array, we can easily determine whether the target would lie to the left or the right of it.

If the target is smaller than the number picked, it would definitely be in the left part of the array. If it is larger, it would be in the right part of the array—if it exists at all.

Now, let's suppose we pick the middle element of the array. By comparing the target with this middle element, we can decide where the target might be. If the target is greater than the middle element, it must be in the right part of the array. If it is smaller, it must be in the left part. If it is equal, we have found our target, so we simply return the index of the middle element.

Let’s say the middle element is at index x, the first index is 0, and the last index of the array (since its length is n) is n-1.

If the target is smaller than the middle element, we narrow down our range to the left part of the array, i.e., from index 0 to x-1.

If the target is larger, we narrow down our range to the right part, i.e., from index x+1 to n-1.

This process of dividing the range in half continues until we find the target.

We keep two pointers: one called low, starting at the beginning of the array, and another called high, starting at the end.

At first, our search range is from low to high.
We calculate the middle element as (low + high) / 2.
If the target is smaller than this middle element, we shift our search range to the left (i.e., low to middle-1).
If the target is greater, we shift our search range to the right (i.e., middle+1 to high).
We continue narrowing down the search range until the low pointer becomes greater than the high pointer. When this happens, it means we’ve searched through the entire array, and the target is not present. In such a case, we return -1, as specified in the problem.

Let’s understand this with an example.
Suppose the array is nums = [1, 2, 3, 4, 5, 6, 7] and the target is 3.
Initially, our range is from index 0 to 6.
The middle element is calculated as (0 + 6) / 2 = 3, corresponding to the value 4 at index 3. Since 4 exceeds the target 3, we narrow our range to 0 to 2.
Now, we recalculate the middle element as (0 + 2) / 2 = 1, corresponding to the value 2 at index 1. Since 2 is smaller than the target 3, we narrow our range to 2 to 2.
The middle element of this range is (2 + 2) / 2 = 2, which corresponds to the value 3 at index 2. Since this equals the target, we return 2.

Binary Search Algorithm Solution
Binary Search Algorithm Solution

What if the target is not present in the array?

If the target is not in the array, this process will eventually cause the low pointer to exceed the high pointer. At that point, we return -1 as instructed by the question.

For example, if the target is 4 and the array is nums = [1, 2, 3], let's go through the steps:

  1. Initially, low = 0 and high = 2 (the indices of the first and last elements). The middle element is calculated as (0 + 2) / 2 = 1 (integer division). The value at index 1 is 2. Since the target 4 is greater than 2, we adjusted our range to low = 2 and high = 2.
  2. Now, with low = 2 and high = 2, we recalculate the middle element as (2 + 2) / 2 = 2. The value at index 2 is 3. Since the target 4 is still greater than 3, we adjust our range to low = 3 and high = 2.
  3. At this point, low > high (i.e., 3 > 2), which means the search range is invalid. This indicates that the target is absent in the array, so we return -1.
Binary Search Algorithm Solution
Binary Search Algorithm Solution

This approach is called a binary search algorithm!

What is binary search?

Binary search is a highly efficient algorithm for finding a target value within a sorted array or list. The idea behind binary search is to repeatedly divide the search space in half, which reduces the search time drastically compared to a linear search. It is a divide and conquer algorithm that efficiently reduces the search space by half with each iteration or recursive call.

When to apply Binary Search Algorithm Solution in a Data Structure:

  1. The data structure must be sorted:
    Binary search works by repeatedly dividing the search space in half. This division is only meaningful if the data is sorted in ascending or descending order, as it ensures that the target can be easily narrowed down to one-half of the array.
  2. The middle element should help minimize or maximize the search space:
    The middle element, calculated as mid = low + (high - low) / 2, acts as the pivot point. If the middle element matches the target, the search is complete. Otherwise, comparing the middle element and the target determines which half of the array to search next, effectively minimizing the search space with each iteration.
  3. The search space must be monotonic:
    The data must exhibit a monotonic property, meaning the values must either consistently increase or decrease across the range. This property ensures that the algorithm can confidently discard the irrelevant half of the search space if the target is smaller or larger than the middle element.

The time complexity of binary search is O(log n) because each step divides the search range in half. At every iteration, we compare the target with the middle element and eliminate half of the array (either the left or right half) from consideration. This halving process continues until the target is found or the range becomes invalid, resulting in a maximum of log₂(n) iterations, where n is the number of elements in the array.

Note: For calculating the middle index in binary search, the formula low + (high - low) / 2 is often preferred over the simpler formula (low + high) / 2. This is because the latter can lead to an integer overflow when the values of low and high are very large, especially in languages like C++ and Java where integers have fixed sizes. By using low + (high - low) / 2, we avoid adding two potentially large numbers directly, thus preventing overflow. This formula ensures that the calculation remains safe and accurate regardless of the size of the array or the range of low and high.

This is how we efficiently search for a target in a sorted array using the binary search algorithm solution, achieving the required O(log n) time complexity.

💡
Try it Yourself!

Binary search example step by step:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 12

  1. Step 1: low = 0, high = 5, mid = (0 + 5) / 2 = 2 → nums[2] = 3. Since 12 > 3, search right → low = 3.
  2. Step 2: low = 3, high = 5, mid = (3 + 5) / 2 = 4 → nums[4] = 9. Since 12 > 9, search right → low = 5.
  3. Step 3: low = 5, high = 5, mid = (5 + 5) / 2 = 5 → nums[5] = 12. Target found at index 5.

Output: 5

0:00
/1:04

How to code it up?

  1. Initialize two pointers, low and high, to define the search range.
  2. Loop while low <= high:
  3. Calculate the middle index as (low + high) / 2 (integer division).
  4. Compare nums[mid] with the target:
    If they are equal, return mid.
    If the target is greater, shift low to mid + 1 (search right half).
    If the target is smaller, shift high to mid - 1 (search left half).
  5. If the loop ends without finding the target, return -1.
Code Implementation of Binary Search
1. Write a program to implement Binary search in C++ language. Try on Compiler 
class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        // Initialize low and high pointers to define the search range
        int low = 0;
        int high = nums.size() - 1;

        // Loop while low <= high to continue searching in the valid range
        while (low <= high) {
            // Calculate the middle index
            int mid = low + (high - low) / 2; // Prevent potential overflow

            // If the middle element is the target, return its index
            if (nums[mid] == target)
                return mid;
            
            // If the target is smaller than the middle element, search in the left half
            else if (nums[mid] > target)
                high = mid - 1;
            
            // If the target is larger than the middle element, search in the right half
            else
                low = mid + 1;
        }

        // If the target is not found, return -1
        return -1;
    }
};

2. Write a program to implement Binary search in Java language. Try on Compiler 
class Solution {
    public int search(int[] nums, int target) {
        
        // Initialize low and high pointers to define the search range
        int low = 0;
        int high = nums.length - 1;

        // Loop while low <= high to continue searching in the valid range
        while (low <= high) {
            // Calculate the middle index
            int mid = low + (high - low) / 2; // Prevent potential overflow

            // If the middle element is the target, return its index
            if (nums[mid] == target)
                return mid;
            
            // If the target is smaller than the middle element, search in the left half
            else if (nums[mid] > target)
                high = mid - 1;
            
            // If the target is larger than the middle element, search in the right half
            else
                low = mid + 1;
        }

        // If the target is not found, return -1
        return -1;
    }
}

3. Write a program to implement Binary search in Python language. Try on Compiler 
class Solution:
    def search(self, nums, target):
        
        # Initialize low and high pointers to define the search range
        low = 0
        high = len(nums) - 1

        # Loop while low <= high to continue searching in the valid range
        while low <= high:
            # Calculate the middle index
            mid = low + (high - low) // 2  # Prevent potential overflow

            # If the middle element is the target, return its index
            if nums[mid] == target:
                return mid
            
            # If the target is smaller than the middle element, search in the left half
            elif nums[mid] > target:
                high = mid - 1
            
            # If the target is larger than the middle element, search in the right half
            else:
                low = mid + 1

        # If the target is not found, return -1
        return -1

4. Write a program to implement Binary search in Javascript language. Try on Compiler 
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {

    // Initialize low and high pointers to define the search range
    let low = 0;
    let high = nums.length - 1;

    // Loop while low <= high to continue searching in the valid range
    while (low <= high) {
        // Calculate the middle index
        let mid = low + Math.floor((high - low) / 2); // Prevent potential overflow

        // If the middle element is the target, return its index
        if (nums[mid] === target) {
            return mid;
        }

        // If the target is smaller than the middle element, search in the left half
        else if (nums[mid] > target) {
            high = mid - 1;
        }

        // If the target is larger than the middle element, search in the right half
        else {
            low = mid + 1;
        }
    }

    // If the target is not found, return -1
    return -1;
}

Time Complexity analysis of Binary Search Solution: O(log n)

The time complexity of this binary search algorithm is O(log n). Here's why:

  1. Halving the search range:
    Initially, the search range is the entire array of size n.
    After the first comparison, the search range is reduced by half, leaving n/2 elements.
    After the second comparison, the search range is reduced to n/4 elements, and so on.
  2. Mathematical Representation:
    After k iterations, the size of the remaining search range will be: n/2ᵏ.
    The process stops when the search range becomes invalid or when we find the target. This occurs when the size of the search range is reduced to 1: n/2ᵏ = 1
  3. Solving for k:
    To find the number of iterations k required for the range to be reduced to 1, solve for k: n = 2ᵏ.
    Taking the logarithm base 2 of both sides: k = log₂(n)
    Thus, the number of iterations is proportional to log₂(n).
  4. Conclusion:
    Since the number of iterations is O(log₂(n)), the time complexity of binary search is O(log n), where n is the number of elements in the array.

Why Logarithmic Complexity:
Each iteration cuts the problem size by half. This halving property is what makes binary search logarithmic in nature. The time complexity grows much slower compared to a linear search (which would be O(n)), making binary search very efficient for large arrays.

Thus, the time complexity is O(log n) because the number of iterations needed to find the target or determine its absence grows logarithmically as the size of the array increases.

Space Complexity: O(1)

The space complexity of this algorithm is O(1).

Here's why:
The algorithm uses only a constant amount of extra space (for the pointers low, high, and mid).
No additional data structures (like arrays or lists) are used that would increase the memory usage with the input size.
Therefore, the space complexity is O(1), making this algorithm highly space-efficient.

Recursive Binary Search Algorithm

The approach we used above was the iterative binary search method, but binary search can also be implemented using a recursive approach. Let’s explore how the recursive binary search works.

In the iterative approach, we used two pointers, low and high, representing the array's start and end. We calculated the middle index as (low + high) / 2 and compared the middle element with the target. If the target is smaller than the middle element, we shifted our search range to the left (i.e., low becomes mid-1, absent the array's start and end). If the target is greater, we shifted our search range to the right (i.e., low becomes mid + 1). low becomes greater than high, which indicates the target is not found, and we return -1.

Now, to do this recursively, we follow the same approach but use function calls instead of a loop. We need a helper function that will take low and high as arguments, along with the array and the target. Here's the idea:

💡
Don't know recursion?
Try this!

Helper Function Definition:

We need a helper function that will take four arguments:

  • nums: The array we are searching through.
  • low: The starting index of the current search range.
  • high: The ending index of the current search range.
  • target: The number we're trying to find in the array.

This function will keep updating the search range and calling itself until it either finds the target or determines it's not in the array.

Base Case (Stopping Condition):

Every recursive function must have a base case, which is the condition under which the function stops calling itself.

For binary search, the base case happens when the low index exceeds the high index. This means that the entire search range has been exhausted, and the target is absent in the array. In this case, we return -1 to indicate the target wasn't found.

Recursive Case (Dividing the Problem):

If the base case isn't met, we calculate the middle index of the current range using:

int mid = (low + high) / 2;

This is the same formula used in the iterative approach. We then compare the middle element of the array with the target.

  • If the middle element is the target, we return the index of the middle element because we found the target.
  • If the target is smaller than the middle element, it means the target must be in the left half of the array. Therefore, we call the function again with the range of low to mid-1recursion depth.
  • If the target is greater than the middle element, it means the target must be in the right half of the array. Therefore, we call the function again with the range mid + 1 to high.

This process of comparing and updating the range continues recursively, with each call reducing the search range by half.

Putting it All Together:
In the main function, we initiate the recursive search by calling the helper function with the initial values for low (0) and high (last index of the array):

The binarySearch function is called with the initial search range from index 0 to the last index (size of the array - 1). If the target is found, the index is returned; if not, -1 is returned.

Binary Search Algorithm Solution

Binary search example step by step:

Consider the array nums = [1, 2, 3, 4, 5, 6, 7] and target = 3:

  1. First call to binarySearch(nums, 0, 6, 3):
    low = 0, high = 6, calculate mid = 3.
    nums[mid] = 4, compare 4 with 3. Since 3 < 4, we search the left half.
    Call binarySearch(nums, 0, 2, 3).
  2. Second call to binarySearch(nums, 0, 2, 3):
    low = 0, high = 2, calculate mid = 1.
    nums[mid] = 2, compare 2 with 3. Since 3 > 2, we search the right half.
    Call binarySearch(nums, 2, 2, 3).
  3. Third call to binarySearch(nums, 2, 2, 3):
    low = 2, high = 2, calculate mid = 2.
    nums[mid] = 3, compare 3 with 3. They are equal, so return 2 (index of the target).

So, the recursive binary search successfully returns 2, the index of the target.

Here's how to code it up:

  1. binarySearch(nums, low, high, target):
  • This function takes the array nums, the search range defined by low and high, and the target value.
  • It first checks the base case, if low is greater than high, meaning the range is invalid, and returns -1 (target not found).
  • It calculates the middle index mid, compares the middle element with the target, and performs recursive calls based on the comparison.
    • If the target is smaller, it searches in the left half (low to mid - 1).
    • If the target is greater, it searches in the right half (mid + 1 to high).
    • If the middle element is equal to the target, it returns the middle index.
  1. search(nums, target):
  • This function is the main entry point, which initializes the search range from the start to the end of the array (0 to length of nums - 1).
  • It calls the binarySearch function to perform the recursive search.
Code Implementation of Binary Search
1. Write a program to implement Binary search in C++ language. Try on Compiler 
class Solution {

    // Helper function for performing binary search recursively
    int binarySearch(vector<int> &nums, int low, int high, int target)
    {

        // Base case: If low exceeds high, target is not in the array
        if(low > high)
            return -1;

        // Calculate the middle index
        int mid = (low + high) / 2;

        // If the middle element is the target, return its index
        if(nums[mid] == target)
            return mid;

        // If the target is greater than the middle element, search in the right half
        else if(nums[mid] < target)
            return binarySearch(nums, mid + 1, high, target);

        // If the target is smaller than the middle element, search in the left half
        else
            return binarySearch(nums, low, mid - 1, target);
    }
    
public:
    // Main function to initiate binary search
    int search(vector<int>& nums, int target) {
        
        // Start the binary search with the full range (0 to nums.size() - 1)
        return binarySearch(nums, 0, nums.size() - 1, target);
    }
};

2. Write a program to implement Binary search in java language. Try on Compiler 
class Solution {

    // Helper function for performing binary search recursively
    public int binarySearch(int[] nums, int low, int high, int target) {

        // Base case: If low exceeds high, target is not in the array
        if (low > high) {
            return -1;
        }

        // Calculate the middle index
        int mid = (low + high) / 2;

        // If the middle element is the target, return its index
        if (nums[mid] == target) {
            return mid;
        }

        // If the target is greater than the middle element, search in the right half
        else if (nums[mid] < target) {
            return binarySearch(nums, mid + 1, high, target);
        }

        // If the target is smaller than the middle element, search in the left half
        else {
            return binarySearch(nums, low, mid - 1, target);
        }
    }

    // Main function to initiate binary search
    public int search(int[] nums, int target) {
        // Start the binary search with the full range (0 to nums.length - 1)
        return binarySearch(nums, 0, nums.length - 1, target);
    }
}

3. Write a program to implement Binary search in Python language. Try on Compiler 
class Solution:

    # Helper function for performing binary search recursively
    def binarySearch(self, nums, low, high, target):

        # Base case: If low exceeds high, target is not in the array
        if low > high:
            return -1

        # Calculate the middle index
        mid = (low + high) // 2

        # If the middle element is the target, return its index
        if nums[mid] == target:
            return mid

        # If the target is greater than the middle element, search in the right half
        elif nums[mid] < target:
            return self.binarySearch(nums, mid + 1, high, target)

        # If the target is smaller than the middle element, search in the left half
        else:
            return self.binarySearch(nums, low, mid - 1, target)

    # Main function to initiate binary search
    def search(self, nums, target):
        # Start the binary search with the full range (0 to len(nums) - 1)
        return self.binarySearch(nums, 0, len(nums) - 1, target)

4. Write a program to implement Binary search in javascript language. Try on Compiler 
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
// Helper function for performing binary search recursively
var binarySearch = function(nums, low, high, target) {

    // Base case: If low exceeds high, target is not in the array
    if (low > high) {
        return -1;
    }

    // Calculate the middle index
    let mid = Math.floor((low + high) / 2);

    // If the middle element is the target, return its index
    if (nums[mid] === target) {
        return mid;
    }

    // If the target is greater than the middle element, search in the right half
    else if (nums[mid] < target) {
        return binarySearch(nums, mid + 1, high, target);
    }

    // If the target is smaller than the middle element, search in the left half
    else {
        return binarySearch(nums, low, mid - 1, target);
    }
}

var search = function(nums, target) {
    // Start the binary search with the full range (0 to nums.length - 1)
        return binarySearch(nums, 0, nums.length - 1, target);
}

Time Complexity analysis of Binary Search Solution: O(log n)

For both recursive and iterative binary search approaches, the time complexity is the same. Here's a detailed explanation:

  1. Divide-and-Conquer Strategy:
    The core idea of binary search is to divide the array into two halves in each step and focus on only one half, based on whether the target is smaller or larger than the middle element.
  2. Problem Reduction:
    At each step, you are reducing the problem size by half. This is why binary search is considered a divide-and-conquer algorithm.
    If the initial array has n elements, after the first step, the search space reduces to n/2. After the second step, it reduces further to n/4, then n/8, and so on.
  3. Iterations:
    Each time the search space is halved, the number of elements left to search is divided by 2. This continues until you either find the target or the search space is empty (low > high).
    The maximum number of steps required to reach a conclusion (either finding the target or concluding it's not in the array) is equal to the number of times you can halve n before you reach 1, which is the logarithm base 2 of n.
  4. Logarithmic Complexity:
    The number of steps in a binary search is log₂(n), where n is the size of the array. This is because you are halving the search space with every step.
    As a result, the time complexity of binary search is O(log n).

In Summary:

  • Time Complexity: O(log n), where n is the number of elements in the array.
  • This is because at each step, the search space is halved, and it takes log₂(n) steps to reduce the search space to just one element or to conclude that the target doesn't exist.

This logarithmic time complexity makes binary search extremely efficient for searching in large, sorted arrays compared to linear search, which has a time complexity of O(n).

Space Complexity: O(log n)

In the recursive approach of binary search, the space complexity primarily depends on the recursive function call stack. Here’s a detailed explanation:

  1. Recursive Call Stack:
    Each time the binary search function is called, a new function call is added to the call stack.
    The depth of recursion corresponds to how many times the array is halved. In the worst case, this depth is equal to log₂(n), where n is the number of elements in the array.
  2. Space used by the Call Stack:
    Since we are dividing the search range into two halves on each recursive call, the function will be called recursively log₂(n) times until the search space is reduced to a single element or the target is found.
    Each recursive call requires space to store local variables (like low, high, and mid) and return addresses. The amount of space used by each call is constant, i.e., O(1).
  3. Total Space Complexity:
    Since there are log₂(n) recursive calls, each of which requires constant space O(1), the total space complexity is O(log n).
    In simpler terms, the space complexity is determined by the maximum depth of the recursion tree, which is log₂(n).

In Summary:

  • Space Complexity: O(log n), where n is the number of elements in the array.
  • This is because of the recursive call stack. Each recursive call consumes O(1) space, and the maximum depth of recursion is log₂(n).

Since the time complexity is the same for both the iterative and recursive approaches, let's focus on comparing their space complexity.

Recursive vs. Iterative Binary Search: Which is Better in Terms of Space?

When comparing recursive and iterative binary search in terms of space complexity, the iterative approach is generally better.

Iterative Binary Search:

In the iterative version, the algorithm only requires a constant amount of space, O(1). This is because it uses a fixed number of variables (low, high, and mid) to track the current search range. Since no function calls are involved, the memory usage does not increase with the input size. Therefore, the space complexity remains constant, making it more space-efficient.

Recursive Binary Search:

In the recursive approach, each function call adds a new stack frame to the call stack. This results in O(log n) space complexity, where n is the size of the array since the maximum recursion depth is proportional to the number of elements in the array (logarithmic depth). Each recursive call holds its own copies of low, high, and mid, contributing to space usage.

Conclusion:

The iterative version is generally better regardingcontributing space complexity because it only uses a constant amount of space. While elegant and easier to understand, the recursive version uses additional space due to the function call stack. stack memory. However, the recursive version can be a good choice if readability and simplicity are prioritized and the input size is manageable.

Real-World Example

Binary search has several real-life applications where searching in a sorted dataset is required. Here are some examples:

  1. Dictionary Lookup: When searching for a word in a dictionary, you instinctively open the book near the middle and determine if the word is in the first half or the second half. This is similar to a binary search.
  2. Contact List in Smartphones: When you search for a contact in your phone, the contacts are sorted alphabetically. The search algorithm uses a method similar to binary search to locate the contact quickly.
  3. Online Shopping Filters: E-commerce platforms often sort items (e.g., by price). When you set filters like a price range, the backend uses binary search to find the items within that range.
  4. Gaming: In some games, binary search is used for collision detection or locating specific game objects in sorted datasets, like finding the nearest enemy in a sorted distance array.
  5. Library Systems: Searching for books by ISBN, title, or author in a catalog system often involves binary search since the data is usually sorted.
  6. Search Engines: When querying sorted databases for specific records (e.g., student IDs or employee IDs), binary search is used to retrieve relevant data quickly.
  7. Medical Diagnosis Systems: Binary search helps narrow possible diagnoses from a sorted list of symptoms and conditions based on input data.

These real-world examples highlight how binary search enables efficient searching when data is organized in a sorted manner.

Binary Search Applications

Binary search has numerous applications across various domains due to its efficiency in searching sorted datasets. Here are some key applications:

  1. Dictionary Lookup: Searching for a word in a dictionary or in autocomplete systems (sorted alphabetically).
  2. Finding Boundaries (First/Last Occurrence): Locating an element's first or last occurrence in a sorted array or determining lower/upper bounds in competitive programming.
  3. E-Commerce Filters: Find products within a price range or search in a sorted product database.
  4. Version Control (Bug Identification): Using binary search to identify the first faulty commit in tools like Git (git bisect).
  5. Optimization Problems: Finding the minimum or maximum value that satisfies a condition, such as allocating resources or minimizing workloads.
  6. Guessing Games: Games like "Guess the Number" are based on binary search principles. With each guess, the range of possible numbers is halved.
  7. Search in Sorted Data Structures: Efficiently searching elements in sorted arrays, databases, or Binary Search Trees (BSTs).

These applications showcase binary search's versatility in solving simple and complex problems efficiently.

Here are the advantages of Binary Search:

  1. High Efficiency:
    Binary search reduces the search space by half in every iteration, making it highly efficient with a time complexity of O(log n). This is much faster than linear search (O(n)), especially for large datasets.
  2. Simplicity:
    The algorithm is conceptually simple and easy to implement, either iteratively or recursively.
  3. Works with Sorted Data:
    Binary search leverages data's sorted nature, making it ideal for datasets with elements arranged in ascending or descending order.
  4. Wide Range of Applications:
    It is widely used in various fields, such as database searching, finding boundaries, solving optimization problems, and even in real-life scenarios like guessing games.
  5. Low Memory Usage (Iterative Approach):
    The iterative version of binary search requires constant space (O(1)) as it does not need additional memory for recursion.
  6. Quick Access to Large Datasets:
    Binary search is well-suited for scenarios where data is large and cannot be sequentially searched, like log files, price filtering, or finding elements in sorted arrays.
  7. Flexibility:
    Binary search can be adapted to solve problems beyond basic element search, such as finding peaks and rotations or solving mathematical equations through bisection methods.
  8. Optimized for Modern Systems:
    Binary search aligns well with systems that perform block or batch data processing, making it efficient for indexed and block-based data storage.

In summary, binary search is a powerful and flexible algorithm, ideal for solving problems efficiently in sorted datasets while using minimal resources.

Here are the disadvantages of Binary Search:

  1. Requires Sorted Data:
    Binary search only works on sorted data. If the data is unsorted, the array or list needs to be sorted first, which can take additional time (O(n log n) for most sorting algorithms) and negates the efficiency of binary search.
  2. Not Suitable for Dynamic Data:
    Maintaining a sorted structure can be expensive for frequently updated datasets, such as inserting or deleting elements. Re-sorting the data after each update can reduce the overall efficiency of the binary search.
  3. Complexity in Some Data Structures:
    Implementing binary search in certain data structures like linked lists is inefficient. For example, linked lists do not support direct access to elements by index, so traversing the list to find the middle element can slow the algorithm.
  4. Overhead in Recursion:
    While the recursive version of binary search is elegant, it introduces overhead from function calls and the risk of stack overflow for very large datasets. The iterative approach can avoid this issue but might be harder to implement in some cases.
  5. Not Always Optimal for Small Data:
    For small datasets, linear search may be more efficient due to lower constant factors in the overhead of binary search's comparisons and index calculations.
  6. Limited Applicability:
    Binary search is primarily effective for searching and optimizing in sorted arrays or data structures. It may not be suitable for problems where sorting or comparison-based searching is not applicable.
  7. Space Complexity in Recursive Approach:
    While the iterative version of binary search has constant space complexity (O(1)), the recursive approach uses stack space proportional to the recursion depth, which could be problematic for very large arrays.

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems.

1. Sqrt(x)

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.You must not use any built-in exponent function or operator.For example, do not use pow(x, 0.5) in C++ or x ** 0.5 in Python.

2. Capacity To Ship Packages Within D Days

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8