Binary Search - Leetcode 704 - Python

Main ideas / concepts

• Binary search problem (LeetCode 704):

  • Input: a sorted (ascending) array nums and a target value.

  • Output: return the index of target if it exists; otherwise return -1 (The subtitles mention “return one,” but the described solution/code returns -1.)

  • Goal: achieve O(log n) time complexity.

• Core strategy (using two pointers):

  • Maintain a search range within the array using two indices:
    • left at the start of the range (initially 0)
    • right at the end of the range (initially len(nums) - 1)
  • Repeatedly check the middle of the current range and eliminate half the remaining candidates based on comparisons.

• Why it’s efficient:

  • Each iteration removes about half of the remaining search space.
  • For an array size n, the number of iterations is about log₂(n), yielding O(log n).

---

Step-by-step algorithm (as described)

1. Initialize

   • left = 0
   • right = len(nums) - 1

2. Loop condition

   • Continue while left <= right
   • This guarantees there is still at least one candidate index to check.

3. Within each loop iteration

   • Compute the middle index:
     • mid = (left + right) // 2 (integer division)
   • Compare:
     • If nums[mid] > target:
       • Target can only be to the left
       • Update: right = mid - 1
     • Else if nums[mid] < target:
       • Target can only be to the right
       • Update: left = mid + 1
     • Else (equal):
       • Return mid immediately (target found)

4. After the loop

   • If the loop ends without returning, the target was not found
   • Return -1

---

Important implementation note (overflow-safe mid calculation)

• Potential bug (in some languages like Java/C++ with 32-bit ints):

  • Computing mid as (left + right) // 2 can overflow when left and right are large.

• Safer method:

  • Compute:
    • mid = left + (right - left) // 2
  • This avoids overflow because right - left is non-negative and stays within bounds.

---

Speakers / sources

• Speaker: Unspecified individual (YouTube channel host/instructor; no name provided in the subtitles).