LeetCode 704. Binary Search

Problem Description

Difficulty: Easy

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.

The solution must run in \(O(\log n)\) time.

Examples:

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

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

Constraints:

1 <= nums.length <= 10000.
-10000 < nums[i], target < 10000

Initial Solution

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1
        while l <= r:
            midpoint = (l + r) // 2
            
            if nums[midpoint] == target:
                return midpoint
            elif nums[midpoint] < target:
                l = midpoint + 1
            elif nums[midpoint] > target:
                r = midpoint - 1
 
        return -1

The classic binary search algorithm. The code first calculates the midpoint of the list and compares the target with the midpoint value. Ultimately, if they don’t match, we discard the side that cannot contain the target. The split is based on the size of the value as the list is sorted in ascending order. By cutting the search space in half at each iteration, we obtain an \(O(\log n)\) solution.

Test Function

def test_binary_search(solution_class):
    """ Test function. Not extensive."""
    # Instantiate the class
    solution = solution_class()

    # Define the test cases
    test_cases = [
        {
            "numbers": [-1,0,3,5,9,12],
            "target": 9,
            "expected": 4
        },
        {
            "numbers": [-1,0,2,4,6,8],
            "target": 3,
            "expected": -1
        }
    ]
    # Iterate over test cases
    for i, test_case in enumerate(test_cases):
        numbers = test_case["numbers"]
        target = test_case["target"]
        expected = test_case["expected"]
        
        # Get the result from the twoSum method
        results = solution.search(numbers, target)
        
        # Check if the result matches the expected output
        if results == expected:
            print(f"Test case {i+1} passed")
        else:
            print(f"Test case {i+1} failed")
            print(f"Expected: {expected}")
            print(f"Got: {results}")

test_binary_search(Solution)

Test case 1 passed
Test case 2 passed

NeetCode Solution

NeedCode’s solution was basically the same, but with the notable exception of the line of code that determines the midpoint (m):

m = l + ((r - l) // 2)

I asked ChatGPT about this, and here’s a summary of the conversation:

Midpoint Calculation: The formula l + ((r - l) // 2) computes the midpoint as follows:

• (r - l) calculates the distance between l and r.
• (r - l) // 2 gives half of this distance (integer division).
• Adding this half-distance to l yields the midpoint.

Overflow Prevention: In programming languages with fixed-size integers (such as Java or C++), calculating the midpoint as (l + r) // 2 can lead to integer overflow when l and r are very large numbers. The alternative formula l + ((r - l) // 2) avoids this issue by performing subtraction before addition, keeping intermediate results within the valid range.

Applicability in Python: While Python’s arbitrary-precision integers prevent overflow errors, using l + ((r - l) // 2) is still beneficial:

• It promotes consistent code across different languages.
• It can be more memory-efficient for very large numbers, avoiding unnecessary allocation for intermediate results.
• It aligns with best practices in algorithm implementation.

This method ensures accurate midpoint calculation while minimizing the risk of overflow in languages with integer limits, and provides a robust solution across various programming environments.