BinarySearch

Binary Search

Problem Description

Implement a binary search algorithm that efficiently finds the position of a target value within a sorted array.

What is Binary Search?

Binary search is a divide-and-conquer algorithm that repeatedly divides the search interval in half. It works only on sorted arrays.

Characteristics

• Time Complexity: O(log n) - much faster than linear search
• Space Complexity:
  • O(1) for iterative implementation
  • O(log n) for recursive implementation (call stack)
• Requirement: Array must be sorted
• Best for: Large sorted datasets

How It Works

1. Compare the target with the middle element
2. If target equals middle element, return the index
3. If target is less than middle, search the left half
4. If target is greater than middle, search the right half
5. Repeat until target is found or the search space is empty

Your Task

Implement the following methods in BinarySearch.java:

1. searchIterative(int[] arr, int target) - Iterative implementation
2. searchRecursive(int[] arr, int target) - Recursive implementation
3. searchRecursive(int[] arr, int target, int left, int right) - Helper method

Test Cases to Consider

• Empty array
• Single element array (found and not found)
• Target at the beginning
• Target at the end
• Target in the middle
• Target not in array
• Even and odd length arrays

Hints

• Use two pointers: left and right
• Calculate middle as left + (right - left) / 2 to avoid overflow
• Be careful with boundary conditions
• For recursion, think about the base case

Common Pitfalls

• Integer overflow when calculating middle: use left + (right - left) / 2 instead of (left + right) / 2
• Off-by-one errors with array indices
• Infinite loops if not updating pointers correctly

Follow-up Questions

1. How would you find the first occurrence of a target in an array with duplicates?
2. How would you find the last occurrence?
3. Can you modify this to find the insertion position for a target not in the array?
4. What's the difference in space complexity between iterative and recursive approaches?

Variants

• Lower bound (find first position where element >= target)
• Upper bound (find first position where element > target)
• Binary search on answer (for optimization problems)

Related Algorithms

• Linear Search
• Jump Search
• Interpolation Search
• Exponential Search