What is Binary Search Algorithm | How to Implement Using JAVA

In today’s article, we are going to discuss binary search algorithms. Binary search is an algorithm employed for efficient searching in a sorted array. By leveraging the fact that the array is sorted, it employs a divide-and-conquer approach to repeatedly divide the search interval in half. This intelligent strategy reduces the time complexity of the algorithm to O(log N), making it highly efficient and faster than other search methods.

Binary search is a powerful algorithm for searching in sorted data structures. While it offers significant advantages in terms of efficiency, there are certain conditions that need to be met in order to apply binary search effectively. Here are the key conditions for utilizing binary search in a data structure:

• Sorted Data: Binary search requires the data structure to be sorted in ascending or descending order. This condition is crucial as binary search relies on the ability to compare elements and make informed decisions based on their relative values. If the data is not sorted, applying binary search would yield incorrect results.
• Random Access: Binary search operates by accessing the middle element of the data structure and subsequently dividing the search space. Therefore, the data structure should support efficient random access to elements. Arrays and certain types of lists, such as ArrayLists, fulfill this requirement as elements can be accessed directly using their indices.
• Static Data: Binary search performs optimally when the data structure remains static or undergoes infrequent updates. Adding or removing elements from a sorted data structure can disrupt the sorted order, requiring additional steps to maintain the integrity of the structure. If the data is frequently updated or dynamically changing, other search algorithms may be more suitable.
• Unique Elements: Binary search assumes that the data structure contains unique elements. If there are duplicate values in the sorted structure, binary search may not guarantee finding the desired element efficiently or may return an arbitrary occurrence of the target value.
• Efficiency Considerations: The benefit of applying binary search becomes more pronounced as the size of the data structure increases. For small collections or datasets, the overhead of dividing the search space may outweigh the advantages of binary search. It is essential to consider the size of the data structure and evaluate whether binary search provides significant performance improvements over alternative search methods.

To understand how binary search works visually, let’s consider a sorted array and walk through the steps of the algorithm using a graphical presentation.

Suppose we have the following sorted array of numbers: [2, 5, 8, 12, 16, 18, 21, 24]. Our goal is to find the index of a target element, let’s say 16.

1. Initial Step:
   • Set the left pointer (L) to the first element (LOW) of the array (index 0) and the right pointer (R) to the last element(HIGH) (index 7).
   • Calculate the middle(MID) index (M) M =L+ (L + R) / 2 or we can say MID = LOW+(HIGH-LOW)/2
2. Comparison Step:
   • Compare the middle element (array[M]) with the target value (16):
     • If array[M] equals the target, the search is successful, and we return M.
     • If array[M] is greater than the target, we set R = M – 1 and go to the next step.
     • If array[M] is less than the target, we set L = M + 1 and go to the next step.
3. Recursion:
   • Repeat steps 1 and 2 with the updated L and R until the target is found or the search space is exhausted.
   • Calculate the new middle index M based on the updated L and R.
   • Compare array[M] with the target and adjust L or R accordingly.
4. Final Step:
   • If the target is found, return the index.
   • If the search space is empty (L > R), the target is not present in the array, and we return an appropriate value indicating the absence.

Here’s a graphical representation of the binary search process for the target value 16 in the given array:

Step 1:
L         M           R
|         |           |
[2, 5, 8, 12, 16, 18, 21, 24]

Step 2:
L     M   R
|     |   |
[2, 5, 8, 12, 16, 18, 21, 24]

Step 3:
      L M R
      | | |
[2, 5, 8, 12, 16, 18, 21, 24]

Step 4:
      L M R
        | |
[2, 5, 8, 12, 16, 18, 21, 24]

Step 5:
      L M R
        | |
[2, 5, 8, 12, 16, 18, 21, 24]

Target Found!
Index: 4

In each step, the middle element is compared to the target, and based on the comparison, the search space is halved by adjusting the left and right pointers. This process continues until the target is found or the search space is exhausted.

Binary Search Complexity

Now, let us explore the time complexity of Binary search in the best case, average case, and worst case scenarios. Additionally, we will examine the space complexity of Binary search.

1. Time Complexity

• Best Case Complexity: The best case occurs when the element being searched is found in the first comparison, meaning the initial middle element is the desired element. In this scenario, the best-case time complexity of Binary search is O(1).
• Average Case Complexity: The average case time complexity of Binary search is O(logn), where n represents the number of elements in the search space. This logarithmic complexity arises from the iterative halving of the search space.
• Worst Case Complexity: The worst case of Binary search transpires when the search space continues to be reduced until only one element remains. In this scenario, the worst-case time complexity of Binary search is O(logn).

2. Space Complexity

The space complexity of binary search is constant, denoted as O(1).

There are two ways to implement the Binary Search Algorithm, which are discussed below.

• Iterative Method
• Recursive Method

The Binary Search Algorithm implemented using the iteration method.

int binarySearch(int array[], int x, int left, int right) {
        // Repeat until the pointers low and high meet each other
        while (left <= right) {
          int mid = left + (right - left) / 2;
          if (array[mid] == x)
            return mid;
          if (array[mid] < x)
            left = mid + 1;
          else
            right = mid - 1;
        }
        return -1;
      }

Recursive Method

 int binarySearch(int array[], int x, int left, int right) {

        if (right >= left) {
            int mid = left + (right - left) / 2;
            // If found at mid, then return it
            if (array[mid] == x)
                return mid;
            // Search the left half
            if (array[mid] > x)
                return binarySearch(array, x, left, mid - 1);
            // Search the right half
            return binarySearch(array, x, mid + 1, right);
        }
        return -1;
    }

Here’s an example of how you can implement the Binary Search algorithm in Java

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

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Check if the target is found
            if (array[mid] == target) {
                return mid;
            }

            // If the middle element is greater, search in the left half
            if (array[mid] > target) {
                right = mid - 1;
            }
            // If the middle element is smaller, search in the right half
            else {
                left = mid + 1;
            }
        }

        // Target element not found
        return -1;
    }

    public static void main(String[] args) {
        int[] array = {2, 5, 8, 12, 16, 18, 21, 24};
        int target = 16;

        int index = binarySearch(array, target);

        if (index != -1) {
            System.out.println("Target found at index: " + index);
        } else {
            System.out.println("Target not found in the array.");
        }
    }
}

Conclusion

We explored the best-case, average-case, and worst-case time complexities of Binary search, which are O(1), O(log n), and O(log n) respectively. This showcases the algorithm’s consistent performance and reliability across various scenarios. Additionally, the space complexity of Binary search is O(1), indicating that it requires only a few constant variables for its execution, regardless of the size of the input.

Binary search can be implemented using either iterative or recursive approaches, with both methods providing the same fundamental principles of dividing and conquering the search space.

Understanding and implementing the Binary Search Algorithm is an essential skill for any programmer or developer. Its efficiency and effectiveness make it a valuable tool in a wide range of applications where fast searching of sorted data is required.

By harnessing the power of Binary search, programmers can optimize their algorithms and improve the overall performance of their applications, leading to enhanced user experiences and increased efficiency.

In summary, the Binary Search Algorithm stands as a fundamental algorithm in computer science, offering a reliable and efficient solution for searching elements in sorted arrays.