Class BinarySearch

java.lang.Object
topics.divideconquer.search.BinarySearch
public class BinarySearch extends Object

Binary Search

A classic Divide and Conquer algorithm used to find the position of a target value within a strictly sorted array. It operates by repeatedly dividing the search interval in half.

Algorithm Steps

  1. Begin with the mid-point of the whole array as a search key.
  2. If the value of the search key is equal to the item, return the index.
  3. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.
  4. Otherwise, narrow it to the upper half.
  5. Repeatedly check until the value is found or the interval is empty.

Complexity Analysis

  • Time Complexity: O(log N) in the worst/average case. O(1) in the best case (found at the first midpoint).
  • Space Complexity (Iterative): O(1) - Requires only a few pointers.
  • Space Complexity (Recursive): O(log N) - Memory consumed by the call stack depth.
Author:
vicegd

  • Constructor Details

    • BinarySearch

      public BinarySearch()

  • Method Details

    • binarySearchIterative

      public int binarySearchIterative(int[] v, int x)
      Iterative implementation of Binary Search. Highly recommended over the recursive version due to O(1) space complexity.
      Parameters:
      v - The strictly sorted array to search in (ascending order).
      x - The target value to locate.
      Returns:
      The index of the target value, or Integer.MIN_VALUE if not found.

    • binarySearchRecursive

      public int binarySearchRecursive(int[] v, int x)
      Recursive implementation of Binary Search. Demonstrates the Divide and Conquer paradigm elegantly, though it incurs O(log N) auxiliary space penalty due to the call stack.
      Parameters:
      v - The strictly sorted array to search in (ascending order).
      x - The target value to locate.
      Returns:
      The index of the target value, or Integer.MIN_VALUE if not found.