Vanilla Binary Search - Binary Search / Overview

Problems
42

I believe almost any algorithm done recursively, so thank you for sharing - but in this case the optimal solution is iterative because the memory is O(1), while the recursive solution is O(log n).

Explanation: Iterative and Recursive Binary Search Algorithm

43

My solution follows. As I worked off the top of my head I calculated mid and adjusted the index on the fly. I did not keep track of left or right, but my solution is more complex as it needed extra checks for array OOB and empty input array. It works, but is not the most efficient solution.

def binary_search(arr: List[int], target: int) -> int:
    if len(arr) == 0:
        return -1
    curr = len(arr) // 2
    
    while arr[curr] != target:
        if curr < 0 or curr >= len(arr) -1:
            return -1
        index = lambda arr, curr : (len(arr) - curr)//2
        
        if arr[curr] < target:
            curr += index(arr, curr)
        else:
             curr -= index(arr, curr)
    
    return curr
44

Regarding the comment:

1. When to terminate the loop

Make sure the while loop has an equality comparison. Otherwise, we’d skip the loop and miss the potential match for the edge case of a one-element array.

I intuitively use an exclusive right element, which means my loop doesn’t use an equality comparison.
i.e.

let left = 0, right = arr.length;
while (left < right) {
  const mid = left + Math.floor((right - left) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] > target) { 
    left = mid + 1
  } else if (arr[mid] > target) {
    right = mid;
  }
}

I wonder if the two approaches are equivalent