Binary Search Algorithm

Binary Search Algorithm is an efficient way to search for an element in a large dataset that can take much more time. It checks each element sequentially, divides the dataset into two halves, and reduces the search time. 

In this article, we will discuss what is a binary search algorithm is, the conditions for applying a binary search algorithm in data structures, the steps of a binary search algorithm, how it works, the implementation of a binary search algorithm in multiple programming languages such as C, C++, Python, and Java, the time and space complexity of the binary search algorithm, its advantages and disadvantages, applications of the binary search algorithm, and a comparison between the binary search algorithm and the linear search algorithm.

Table of Contents:

• What is the Binary Search Algorithm?
• Conditions for Using the Binary Search Algorithm in Data Structures
• Steps of the Binary Search Algorithm
• How the Binary Search Algorithm Works
• How to Implement the Binary Search Algorithm
• Iterative Binary Search Algorithm
• Recursive Binary Search Algorithm
• Time & Space Complexity of Binary Search Algorithm
• Applications of the Binary Search Algorithm
• Advantages of the Binary Search Algorithm
• Disadvantages of the Binary Search Algorithm
• Linear Search Algorithm vs. Binary Search Algorithm
• Conclusion

What is the Binary Search Algorithm?

Binary Search Algorithm (BSA) is a searching algorithm that is used to find an element in a sorted array. It uses the divide-and-conquer principle, as it divides the search space into two halves repeatedly by comparing the target element with the middle element until the target element is found or the search space becomes empty.

Conditions for Using the Binary Search Algorithm in Data Structures

Below are the conditions that you must follow to apply the binary search algorithm in data structures:

• The dataset must be sorted either in ascending or descending order.
• The data structure should support O(1) access to elements.
• The dataset must be static or fixed.
• The data structure should allow for comparison.

Steps of the Binary Search Algorithm

Below are a few steps of the binary search algorithm that must be followed for an efficient search:

Step 1: Initialize the boundaries within the search space.

Set low = 0, which is the start of the list or array, and high = n-1, which is the end of the list or array.

Step 2: Divide the search space into two halves and repeat this process until low > high.

Calculate the middle index:

mid = low + (high – low) / 2

Step 3: Now, compare the middle element with the target element in the search space.

• Condition 1: If arr[mid] == target, then the mid element is found.
• Condition 2: If arr[mid] > target, then search in the left half of the search space by updating high = mid – 1.
• Condition 3: If arr[mid] < target, then search in the right half of the search space by updating low = mid +1.

Step 4: Repeat steps 2 and 3 until the target element is found.

Step 5: Now, check the result that is returned by the process.

• If the result is an index, then the target element is found.
• If the result is -1, then the target element is not found.

How the Binary Search Algorithm Works

The pseudocode of the binary search algorithm will help you to understand its working in an efficient and better manner.

BinarySearch(arr, target):
    low <- 0
    high <- length(arr) - 1
    WHILE low ≤ high:
        mid <- (low + high) // 2   // Calculate the middle index
        IF arr[mid] = target:
            RETURN mid   // Target is found
        ELSE IF arr[mid] < target:
            low <- mid + 1  // Search in the right half
        ELSE:
            High <- mid - 1  // Search in the left half
    RETURN -1  // Target is not found

How to Implement the Binary Search Algorithm

The binary search algorithm can be implemented by using the two methods given below:

1. Iterative Binary Search Algorithm 
2. Recursive Binary Search Algorithm 

Iterative Binary Search Algorithm

In an iterative binary search algorithm, a loop is used to search for a target element in the given search space. 

Let’s understand the implementation of the iterative binary search algorithm with the help of examples in different programming languages:

1. Binary Search Algorithm in C

Output:

2. Binary Search Algorithm in C++

Output:

3. Binary Search Algorithm in Python

Output:

4. Binary Search Algorithm in JAVA

Output:

Recursive Binary Search Algorithm

The recursive binary search algorithm finds a target element in the searching space by splitting it into two halves and recursively calling itself until it finds the target element, where it uses the divide-and-conquer principle.

Let’s understand the implementation of the recursive binary search algorithm with examples from various programming languages:

1. Binary Search Algorithm in C

Output:

2. Binary Search Algorithm in C++

Output:

3. Binary Search Algorithm in Python

Output:

4. Binary Search Algorithm in JAVA

Output:

Time & Space Complexity of Binary Search Algorithm

Both the space and time complexity of the binary search algorithm depend on how it works. Now, let’s understand each separately.

Time Complexity Analysis of Binary Search

As we have discussed above, the binary search algorithm works by repeatedly dividing the search space into two halves until the target element is found; thus, it is a bit faster.

Space Complexity Analysis of Binary Search

The binary search algorithm needs only minimal extra memory, as it only uses a few integer variables such as low, high, and mid.

Applications of the Binary Search Algorithm

• The binary search algorithm is used in sorted data structures such as arrays and lists for faster retrieval of elements.
• It is used in Binary Search Trees (BST) for the insertion and deletion of elements.
• It is also used in optimization problems, search engines, computer networks, operating systems, e-commerce platforms, and stock market analysis.

Advantages of the Binary Search Algorithm

1. The binary search algorithm provides efficient and fast searching.
2. It is ideal to use in large, sorted arrays and lists.
3. The binary search algorithm is easy to implement as it has basic logic and needs only a few lines of code.
4. Binary search algorithm uses only a few variables; thus, the iterative approach of binary search runs with O(1) space complexity.
5. It is useful in problems such as finding the lower or upper bound of a value in a sorted dataset.
6. A binary search algorithm is very efficient in insertions and deletions in static data structures.
7. It is widely used in real-world applications such as search engines, operating systems, and computer networks.

Disadvantages of the Binary Search Algorithm

1. The binary search algorithm only works on sorted data structures.
2. It is not suitable for small datasets for implementing operations.
3. The recursive binary search algorithm needs extra space because of recursive calls.
4. It is inefficient for the linked lists because in the linked list,
5. Directly accessing the middle element is not possible.
6. The binary search algorithm cannot be applied to unstructured data such as graphs, hash tables,  and unordered lists.

Linear Search Algorithm vs. Binary Search Algorithm

Conclusion

As we have discussed in this article, the binary search algorithm is a very efficient and fast searching algorithm and can be used for sorted data structures. It can be implemented in two ways: iterative and recursive. Also, the binary search algorithm is faster than the linear search algorithm. So, by understanding the concept of the binary search algorithm, its implementation, advantages and disadvantages, complexity analysis, and comparison with the linear search algorithm, you can easily use it whenever you need to in different programming languages.

FAQs on Binary Search Algorithm