Binary Search Iterative Approach in DSA Typescript

Mental Model

Binary search finds a target by repeatedly cutting the search area in half until the target is found or no area remains.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if the word is before or after that page, and repeating this process on the smaller section.

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0  1  2  3  4   5   6
Pointers:  low ↑                 high ↑
           mid ↑

Dry Run Walkthrough

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

Goal: Find the index of target 9 in the array using iterative binary search

Step 1: Calculate mid index between low=0 and high=6

low=0, mid=3, high=6, array[mid]=7

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

Step 2: Since 9 > 7, move low to mid+1=4

low=4, high=6

Why: Target must be in right half, so we discard left half

Step 3: Calculate new mid between low=4 and high=6

low=4, mid=5, high=6, array[mid]=11

Why: Check middle of new search area

Step 4: Since 9 < 11, move high to mid-1=4

low=4, high=4

Why: Target must be in left half, so discard right half

Step 5: Calculate mid between low=4 and high=4

low=4, mid=4, high=4, array[mid]=9

Why: Only one element left to check

Step 6: Found target at mid=4, return index 4

Target found at index 4

Why: Search complete

Result:

Index 4 where value 9 is located

Annotated Code

DSA Typescript

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

    while (low <= high) {
      const mid = Math.floor((low + high) / 2) // find middle index
      if (arr[mid] === target) {
        return mid // target found
      } else if (arr[mid] < target) {
        low = mid + 1 // search right half
      } else {
        high = 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 found at index ${result}`)
} else {
  console.log('Target not found')
}

const mid = Math.floor((low + high) / 2) // find middle index

Calculate middle index to split search area

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

Check if middle element is target

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

If target is greater, move low pointer to right half

else { high = mid - 1 }

If target is smaller, move high pointer to left half

Output

Target 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 reducing search steps exponentially

Edge Cases

Empty array

Returns -1 immediately as low > high

DSA Typescript

while (low <= high)

Target not in array

Search space shrinks until low > high, then returns -1

DSA Typescript

while (low <= high)

Single element array with target present

Checks single element and returns index if matches

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 iterative approach because it efficiently halves the search space each step.

Common Mistakes

Mistake: Using (low + high) / 2 without floor, causing mid to be a float
Fix: Use Math.floor to get an integer middle index

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

Summary

Finds the position of a target value in a sorted array by repeatedly halving the search range.

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

The key insight is cutting the search space in half each step to find the target efficiently.