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):

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):

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)

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

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)

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