Understanding Binary Search: A Complete Guide

When to use binary search?

Use binary search when→

1. The dataset is sorted

   binary search only works on only sorted arrays

2. Fast lookups are needed

   With a time complexity of O(log n), binary search is much faster than linear search (O(n)) for large datasets.

3. Searching in a large dataset

   When the number of elements is large (e.g., millions of records), binary search is efficient compared to linear search.

Algorithm (Iterative Approach)

1. Set low = 0 and high = n - 1 (where n is the array size).

2. While low ≤ high:

   • Compute mid = (low + high) / 2.

   • If arr[mid] == target, return mid (element found).

   • If arr[mid] < target, search the right half (low = mid + 1).

   • If arr[mid] > target, search the left half (high = mid - 1).

3. If not found, return -1.

Time Complexity of Binary Search

Binary Search works by dividing the search space in half at each step. This results in a logarithmic time complexity:

Derivation of O(log n)

• Each step reduces the search space by half.

• If the array has n elements, the number of times we can halve n before we reach 1 element is log₂(n).

• Mathematically, the recurrence relation is:

$$T(n)=T(n/2)+O(1)$$

• which solves to O(log n).

Space Complexity

• O(1) for iterative binary search (only a few variables are used).

• O(log n) for recursive binary search (due to recursive function call stack).

// import static org.junit.jupiter.api.Assertions.assertEquals;

// import org.junit.jupiter.api.Test;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter number to search between  1, 12, 33, 46, 75, 86, 98, 498");
    int target = sc.nextInt();
    int[] arr = { 1, 12, 33, 46, 75, 86, 98, 498 };
    int x = binarySearch(arr, target);
    if (x == 1) {
      System.out.println("Found");
    } else {
      System.out.println("Not Found");
    }
  }

  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) {
        start = mid + 1;
      } else if (arr[mid] > target) {
        end = mid - 1;
      } else {
        return 1;
      }
    }
    return -1;
  }
}