Binary Search as Divide and Conquer in DSA Typescript

Mental Model

Binary search splits a sorted list into halves to quickly find a target by ignoring half the list each time.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding to look in the left or right half depending on the word you want.

Sorted array: [1, 3, 5, 7, 9, 11, 13]
Indexes:     [0, 1, 2, 3, 4,  5,  6]
Start -> 0 ↑
End -> 6
Mid -> 3 (value 7)

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13], target: 9

Goal: Find the index of target 9 using binary search

Step 1: Calculate mid index between start=0 and end=6

[1, 3, 5, 7, 9, 11, 13]
start=0, mid=3 (7), end=6

Why: We check the middle element to decide which half to search next

Step 2: Compare target 9 with mid value 7; target is greater, so move start to mid+1=4

[1, 3, 5, 7, 9, 11, 13]
start=4, end=6

Why: Since 9 > 7, target must be in the right half

Step 3: Calculate new mid index between start=4 and end=6

[1, 3, 5, 7, 9, 11, 13]
start=4, mid=5 (11), end=6

Why: Check middle of the new search range

Step 4: Compare target 9 with mid value 11; target is smaller, so move end to mid-1=4

[1, 3, 5, 7, 9, 11, 13]
start=4, end=4

Why: Since 9 < 11, target must be in the left half

Step 5: Calculate new mid index between start=4 and end=4

[1, 3, 5, 7, 9, 11, 13]
start=4, mid=4 (9), end=4

Why: Only one element left to check

Step 6: Compare target 9 with mid value 9; they are equal, return index 4

[1, 3, 5, 7, 9, 11, 13]
Found target at index 4

Why: Target found, stop searching

Result:

[1, 3, 5, 7, 9, 11, 13]
Target 9 found at index 4

Annotated Code

DSA Typescript

class BinarySearch {
  static search(arr: number[], target: number): number {
    let start = 0
    let end = arr.length - 1

    while (start <= end) {
      const mid = Math.floor((start + end) / 2) // find middle index
      if (arr[mid] === target) {
        return mid // target found
      } else if (arr[mid] < target) {
        start = mid + 1 // search right half
      } else {
        end = mid - 1 // search left half
      }
    }
    return -1 // target not found
  }
}

// Driver code
const array = [1, 3, 5, 7, 9, 11, 13]
const target = 9
const result = BinarySearch.search(array, target)
if (result !== -1) {
  console.log(`Target ${target} found at index ${result}`)
} else {
  console.log(`Target ${target} not found`)
}

const mid = Math.floor((start + end) / 2)

Calculate middle index to split array

if (arr[mid] === target) { return mid }

Check if middle element is the target

else if (arr[mid] < target) { start = mid + 1 }

If target is greater, discard left half by moving start

else { end = mid - 1 }

If target is smaller, discard right half by moving end

Output

Target 9 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space until the target is found or space is empty

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted arrays by skipping half the elements each step

Edge Cases

Empty array

Returns -1 immediately since start > end

DSA Typescript

while (start <= end)

Target not in array

Search space shrinks until start > end, then returns -1

DSA Typescript

while (start <= end)

Single element array with target present

Checks the only element and returns its index

DSA Typescript

if (arr[mid] === target) { return mid }

When to Use This Pattern

When you need to find an item quickly in a sorted list, use binary search because it divides the problem in half each time, making it very fast.

Common Mistakes

Mistake: Calculating mid as (start + end) / 2 without floor, causing float index
Fix: Use Math.floor to get an integer index

Mistake: Not updating start or end correctly, causing infinite loop
Fix: Ensure start = mid + 1 or end = mid - 1 to shrink search space

Mistake: Using binary search on unsorted array
Fix: Sort the array first or use linear search

Summary

Binary search finds a target in a sorted list by repeatedly dividing the search range in half.

Use it when you have a sorted list and want to find an element quickly.

The key insight is that each comparison lets you ignore half the remaining elements.