Day 6: Binary Search Algorithm

---

Binary Search Overview

• Binary search is a fast search algorithm that works on sorted arrays. It repeatedly divides the search interval in half, reducing the search space by half with each iteration.

• It has a time complexity of O(log n) where "n" is the number of elements in the array. This makes it much more efficient than linear search for large data sets.

Java Code for Binary Search

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

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (arr[mid] == target) {
                return mid; // Return the index where the target is found
            } else if (arr[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return -1; // Return -1 if the target is not found
    }

    public static void main(String[] args) {
        int[] arr = { 2, 4, 6, 8, 10, 12, 14 };
        int target = 8;
        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("Element found at index " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

Binary Search Algorithm

Binary search works by repeatedly dividing the search range in half until the desired element is found or the search range becomes empty.

1. Start with a sorted array: Binary search requires that the input array is sorted in ascending order.

2. Initialize variables:

   • left - The index of the leftmost element in the search range (initially 0).

   • right - The index of the rightmost element in the search range (initially the length of the array minus 1).

3. Repeat until the search range is empty: a. Calculate the middle index as mid = (left + right) / 2. b. Compare the element at the middle index with the target element. c. If the middle element is equal to the target, return its index (search successful). d. If the middle element is less than the target, update left to mid + 1. e. If the middle element is greater than the target, update right to mid - 1.

4. If the loop exits without finding the target, return -1 to indicate that the element is not in the array.

Finding Mid-term

• The below-mentioned two expressions are used to calculate the middle index of a range, typically for binary search or similar algorithms. However, the first expression:

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

• is preferred over the second expression:

•   int mid = (left + right) / 2;
  

• The reason for this preference is to avoid potential integer overflow issues. The first expression ensures that the subtraction right - left is performed before dividing by 2. This is important because if left and right are very large integers, directly adding them together could result in an integer overflow, which may lead to incorrect results or undefined behavior.

• By subtracting left from right first and then dividing by 2, you avoid this potential overflow problem and ensure the correct middle index is calculated, even for large values of left and right. Therefore, the first expression is a safer and more robust way to calculate the middle index in practice.

Order-Agnostic Binary-Search

• The above code is good if we know that the array is sorted in ascending order, but what if we don't know whether it is sorted in ascending or descending order?

• That's where Order-agnostic binary search comes into play.

Java Code for Order-Agnostic Binary Search

public class Main {
    public static int orderAgnosticBS(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;

        // Determine the order of the array (ascending or descending)
        boolean isAscending = arr[start] < arr[end];

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (arr[mid] == target) {
                return mid; // Return the index where the target is found
            }

            if (isAscending) {
                if (arr[mid] < target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            } else {
                if (arr[mid] > target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }

        return -1; // Return -1 if the target is not found
    }

    public static void main(String[] args) {
        int[] ascendingArr = { 2, 4, 6, 8, 10, 12, 14 };
        int[] descendingArr = { 14, 12, 10, 8, 6, 4, 2 };

        int target = 8;
        int ascendingResult = orderAgnosticBS(ascendingArr, target);
        int descendingResult = orderAgnosticBS(descendingArr, target);

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

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

Use Cases

• Binary search is highly efficient and suitable for large sorted data sets.

• It is commonly used in situations where you need to quickly find an element in a sorted list, such as searching in a sorted array or a dictionary.

Performance

• Binary search has a time complexity of O(log n), making it very efficient for large data sets.

• It divides the search space in half with each iteration, leading to fast search times.

• For you to understand how efficient it is, let's take an example array of 1 million elements. In the worst-case scenario in a linear search algorithm, 1 million comparisons are made. However, in binary search algorithms, only 20 comparisons are made. I hope now you can understand the difference.

Conclusion

• Binary search is a powerful and efficient algorithm for searching in sorted data sets.

• It outperforms linear search for large data sets but requires that the data be sorted beforehand.

• When you need to find elements in a sorted list, binary search is a top choice.