# NEETCODE - Binary Search: Binary Search

The Foundation of Logarithmic Search - From O(n) to O(log n)

Technology: **Python, Algorithms**  
Skill: **Binary Search, O(log n)**

## 1. Problem Statement

You are given an array of **distinct integers** `nums`, sorted in **ascending order**, and an integer `target`.

Implement a function to search for `target` within `nums`. If it exists, then return its index; otherwise, return `-1`.

Your solution must run in **O(log n)** time.

**Example 1:**

`Input: nums = [-1,0,2,4,6,8], target = 4  
Output: 3`

**Example 2:**

`Input: nums = [-1,0,2,4,6,8], target = 3  
Output: -1`

**Constraints:**

- `1 <= nums.length <= 10000`
- `-10000 < nums[i], target < 10000`
- All integers in `nums` are **distinct**
- `nums` is sorted in **ascending order**

**Edge Cases to Consider:**

- Single element array: `[5]`, target = 5 or target = 3
- Target is the first element
- Target is the last element
- Target is in the middle
- Target doesn't exist (smaller than all, larger than all, or in between)
- Array with two elements

## 2. Your Solution Review & Feedback

### What You Implemented

You wrote two recursive implementations of binary search, both excellent! Let me analyze each:

**First Implementation (Nested Function with Offset):**

```python
from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binary_search(nums, target, offset=0):
            if len(nums) < 1:
                return -1
            mid_index = len(nums) // 2
            if target == nums[mid_index]:
                return mid_index + offset
            elif target < nums[mid_index]:
                left_bisection = nums[:mid_index]
                return binary_search(left_bisection, target, offset)
            elif target > nums[mid_index]:
                right_bisection = nums[mid_index + 1:]
                new_offset = offset + mid_index + 1
                return binary_search(right_bisection, target, new_offset)
        return binary_search(nums=nums, target=target)
```

**Second Implementation (Method-Based with Offset):**

```python
class Solution:
    def search(self, nums, target, offset=0):
        l = len(nums)
        if l == 0:
            return -1
        middle_index = l // 2
        middle_value = nums[middle_index]
        if middle_value == target:
            return middle_index + offset
        elif middle_value > target:
            new_array = nums[:middle_index]
            return self.search(new_array, target, offset)
        elif middle_value < target:
            new_array = nums[middle_index + 1:]
            offset += middle_index + 1
            return self.search(new_array, target, offset)
```

### What Worked Well

Both implementations are excellent and show mastery:

- ✅ **Perfect offset tracking**
- ✅ **Correct base cases**
- ✅ **Proper slicing for right half**
- ✅ **Good debugging**

### Issues Identified

**Both implementations share the same optimization opportunity:**

- Array slicing creates copies (O(n) space and time)

### Recommended Improvements

**Optimization 1: Iterative Approach (No Array Copying)**

```python
def search(self, nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
```

**Optimization 2: Recursive with Index Pointers**

```python
def search(self, nums: List[int], target: int) -> int:
    def binary_search_helper(left, right):
        if left > right:
            return -1
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            return binary_search_helper(mid + 1, right)
        else:
            return binary_search_helper(left, mid - 1)
    return binary_search_helper(0, len(nums) - 1)
```

## 3. Solutions Progression

### Approach 1: Linear Search (Naive)

```python
from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for index in range(len(nums)):
            if nums[index] == target:
                return index
        return -1
```

**Time Complexity:** O(n)

**Space Complexity:** O(1)

### Approach 2: Recursive Binary Search with Array Slicing

### Approach 3: Recursive Binary Search with Index Pointers

### Approach 4: Iterative Binary Search

## 4. Pattern Recognition

### Core Algorithmic Pattern: **Binary Search / Divide and Conquer**

### Key Insight That Unlocks the Problem

**The "Aha!" Moment:**

**Naive thinking:** "I'll check each element one by one."  
**Breakthrough insight:** "The array is sorted! If the middle element is too small, I can ignore everything to the left. If it's too large, I can ignore everything to the right."

## 5. Bridge to Real Systems

### Real-World Applications:

- Database indexing (B-trees use binary search)
- Git bisect (finding which commit introduced a bug)

## 6. Common Mistakes

### Mistake 1: Wrong Loop Condition

**Fix:** Use `while left <= right:`  
### Mistake 2: Off-by-One in Range Update

**Fix:** Use `left = mid + 1` and `right = mid - 1`
### Mistake 3: Wrong Initial Right Boundary

**Fix:** Use `right = len(nums) - 1`

## 7. Key Takeaways

### 1. **Binary Search is About Halving**  
### 2. **Your Recursive Solutions Are Correct**  
### 3. **The Iterative Pattern is Standard**  
### 4. **Real Systems Use This Everywhere**

## 8. Complexity Summary Table

| Approach | Time | Space | Notes |
| --- | --- | --- | --- |
| **Linear Search** | O(n) | O(1) | Doesn't use sorted property |
| **Recursive (slicing)** | O(log n) comparisons, O(n) slicing | O(n) | Correct and elegant! |
| **Recursive (pointers)** | O(log n) | O(log n) | No slicing overhead |
| **Iterative** | O(log n) | O(1) | Production standard |