Master Binary Search Algorithm- Why and How | Implementation

In the previous article , we learnt about the searching algorithms and two types of searching algorithms. We learnt about Linear Search algorithm. In this article, we will learn about another important searching algorithm called Binary Search algorithm.

About Binary Search Algorithm

Binary search is an efficient algorithm designed to locate a specific value within a sorted array or list. It achieves this by continuously dividing the search range in half until the target value is either found or determined to be absent.

Here’s how the binary search algorithm works:

1. Input: Start with a sorted array or list of elements and a target value to search for.
2. Initialization: Define two pointers, left and right, which point to the first and last elements of the array, respectively.
3. Search Process:
4. At each iteration, calculate the midpoint of the current segment (using mid = (left + right) / 2 or mid = (left + right) >> 1).
5. Compare the middle element with the target value.
   • If they match, return the index of the middle element, indicating the search is successful.
   • If the target is smaller than the middle element, adjust the right pointer to mid - 1, reducing the search space to the left half.
   • If the target is larger than the middle element, move the left pointer to mid + 1, reducing the search space to the right half.
6. Repeat the search steps until the target is found or the pointers cross, indicating the target is not present in the array.

Problem Statement-Binary Search Algorithm

Given a sorted array arr of size N and a target element, the task is to determine the position of the target element in the array. If the element is not present, the function should return a result indicating that.

Here’s a java code of binary search algorithm(Iterative code):

public class BinarySearch {
    // Iterative method for binary search
    static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

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

            // Check if target is at mid
            if (arr[mid] == target)
                return mid;

            // If target is larger, disregard left half
            if (arr[mid] < target)
                left = mid + 1;
            // If target is smaller, disregard right half
            else
                right = mid - 1;
        }

        // If target is not in the array
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;
        int result = binarySearch(arr, target);
        if (result == -1)
            System.out.println("Element not found in array");
        else
            System.out.println("Element found at index " + result);
    }
}

Recursive Approach for Binary Search Algorithm:

public class BinarySearch {
    // Recursive method for binary search
    static int binarySearch(int[] arr, int target, int left, int right) {
        if (left <= right) {
            int mid = left + (right - left) / 2;

            // Check if target is at mid
            if (arr[mid] == target)
                return mid;

            // If target is smaller, search left subarray
            if (arr[mid] > target)
                return binarySearch(arr, target, left, mid - 1);

            // Otherwise, search right subarray
            return binarySearch(arr, target, mid + 1, right);
        }

        // Target is not in the array
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;
        int result = binarySearch(arr, target, 0, arr.length - 1);
        if (result == -1)
            System.out.println("Element not found in array");
        else
            System.out.println("Element found at index " + result);
    }
}

The key advantage of binary search is its efficiency. With each comparison, binary search halves the size of the search space, making it particularly useful for large datasets.

Complexity of Binary Search Algorithm:

• Time-Complexity: O(logn)
• Space-Complexity: O(1)

The logarithmic time complexity means that binary search can efficiently handle even massive datasets.