Binary Search

Binary Search is an efficient algorithm for finding the position of a target element within a sorted array. Unlike Linear Search, which checks elements one by one, Binary Search eliminates half of the remaining elements in each step, making it significantly faster for large datasets.

Binary Search Logic

The core principle of Binary Search relies on divide and conquer. Here's how the logic works:

1. Start with two pointers: one at the beginning (low) and one at the end (high) of the array.

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

3. Compare the middle element with the target:

   • If arr[mid] == target, return mid.

   • If arr[mid] < target, ignore the left half by setting low = mid + 1.

   • If arr[mid] > target, ignore the right half by setting high = mid - 1.

4. Repeat steps 2 and 3 until low > high or the element is found.

Binary Search only works on sorted arrays. If the array is unsorted, it must be sorted first (with an O(n log n) cost).

---

Binary Search in Java

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

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == target) {
                return mid;  // Element found
            } else if (arr[mid] < target) {
                low = mid + 1;  // Search in right half
            } else {
                high = mid - 1;  // Search in left half
            }
        }

        return -1;  // Element not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5, 6, 8, 9};
        int target = 6;
        int result = binarySearch(arr, target);

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

---

Binary Search in C

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;  // Element found
        } else if (arr[mid] < target) {
            low = mid + 1;  // Search right
        } else {
            high = mid - 1;  // Search left
        }
    }

    return -1;  // Element not found
}

int main() {
    int arr[] = {1, 2, 4, 5, 6, 8, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 6;

    int result = binarySearch(arr, size, target);

    if (result != -1) {
        printf("Element %d found at index %d.\n", target, result);
    } else {
        printf("Element %d not found in the array.\n", target);
    }

    return 0;
}

---

Time Complexity Analysis

Let n be the number of elements in the array.

• Best Case: O(1) – when the middle element is the target.

• Average and Worst Case: O(log n) – each comparison cuts the search space in half.

Mathematical Justification:

• The maximum number of comparisons required to search in n elements is:

  log⁡2(n)+1\log_2(n) + 1

This makes Binary Search exponentially faster than Linear Search for large datasets.

---

Space Complexity

• Binary Search has a space complexity of O(1) in the iterative version.

• If implemented recursively, the space complexity becomes O(log n) due to the function call stack.

---

Key Requirements

• The array must be sorted. If not, sort it before applying Binary Search.

• Binary Search is not suitable for frequently changing datasets unless the array remains sorted at all times.

---

Summary

Criteria	Linear Search	Binary Search
Time Complexity	O(n)	O(log n)
Array Requirement	Unsorted OK	Sorted Required
Best Case	O(1)	O(1)
Space Complexity	O(1)	O(1) iterative, O(log n) recursive
Suitable For	Small datasets, Unsorted data	Large, sorted datasets

Binary Search is a powerful and efficient searching technique for sorted data. Understanding it thoroughly also builds the foundation for advanced algorithms like Binary Search Trees and many divide-and-conquer algorithms.