# 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