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.

Practice

1. What is the main purpose of the Binary Search Iterative Approach in a sorted array?

easy

A. To find the maximum value in the array

B. To sort the array elements in ascending order

C. To reverse the array elements

D. To find the position of a target value efficiently by repeatedly dividing the search interval in half

Solution

1. Step 1: Understand the goal of binary search

   Binary search is used to find a target value in a sorted array by dividing the search space repeatedly.

2. Step 2: Identify the iterative approach

   The iterative approach uses a loop to narrow down the search range until the target is found or the range is empty.

3. Final Answer:

   To find the position of a target value efficiently by repeatedly dividing the search interval in half -> Option D

4. Quick Check:

   Binary search = efficient target search [OK]

Hint: Binary search halves the search space each step [OK]

Common Mistakes:

• Confusing binary search with sorting algorithms
• Thinking binary search works on unsorted arrays
• Assuming it finds max/min values

2. Which of the following is the correct way to initialize the middle index in an iterative binary search in TypeScript?

easy

A. const mid = (low + high) / 2;

B. const mid = Math.floor((low + high) / 2);

C. const mid = Math.ceil((low + high) / 2);

D. const mid = low + high;

Solution

1. Step 1: Understand index calculation in binary search

   The middle index must be an integer index, so we use Math.floor to round down the division result.

2. Step 2: Check each option

   const mid = (low + high) / 2; returns a float, const mid = Math.floor((low + high) / 2); correctly floors the value, const mid = Math.ceil((low + high) / 2); rounds up which can cause errors, const mid = low + high; sums indices without division.

3. Final Answer:

   const mid = Math.floor((low + high) / 2); -> Option B

4. Quick Check:

   Use Math.floor for middle index [OK]

Hint: Always floor the average of low and high [OK]

Common Mistakes:

• Using division without flooring causing float index
• Using ceil which may skip elements
• Adding indices without dividing

3. What will be the output of the following TypeScript code snippet?

function binarySearch(arr: number[], target: number): number {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

const result = binarySearch([2, 4, 6, 8, 10], 6);
console.log(result);

medium

A. 2

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace the binary search for target 6

   Initial low=0, high=4, mid=2 (element 6). arr[mid] equals target, so return 2.

2. Step 2: Confirm output

   Function returns index 2, which is printed.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Check mid index value matches target first [OK]

Common Mistakes:

• Off-by-one errors in index calculation
• Returning wrong index when target found
• Confusing return value with element value

4. Identify the bug in this iterative binary search code snippet and select the correct fix:

function binarySearch(arr: number[], target: number): number {
  let low = 0;
  let high = arr.length;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

medium

A. Change let high = arr.length; to let high = arr.length - 1;

B. Change low <= high to low < high

C. Change mid = Math.floor((low + high) / 2); to mid = Math.ceil((low + high) / 2);

D. Remove the else before if (arr[mid] < target)

Solution

1. Step 1: Identify the initialization error

   High should be the last valid index, which is arr.length - 1, not arr.length.

2. Step 2: Understand impact of wrong high value

   Setting high to arr.length causes out-of-bound access at arr[mid] when mid equals arr.length.

3. Final Answer:

   Change let high = arr.length; to let high = arr.length - 1; -> Option A

4. Quick Check:

   High index must be last valid array index [OK]

Hint: High index = array length minus one [OK]

Common Mistakes:

• Setting high to array length causing out-of-bounds
• Changing loop condition incorrectly
• Using ceil instead of floor for mid

5. Given a sorted array with possible duplicate values, how can you modify the iterative binary search to find the first occurrence of a target value?

hard

A. When arr[mid] equals target, update low to mid + 1 and continue searching right

B. Return mid immediately when arr[mid] equals target

C. When arr[mid] equals target, update high to mid - 1 and continue searching left

D. Use recursion instead of iteration

Solution

1. Step 1: Understand the problem with duplicates

   Standard binary search returns any occurrence, not necessarily the first.

2. Step 2: Modify search to find first occurrence

   When target found at mid, move high to mid - 1 to continue searching left side for earlier occurrence.

3. Step 3: Keep track of potential answer

   Store mid as potential answer and continue until low > high.

4. Final Answer:

   When arr[mid] equals target, update high to mid - 1 and continue searching left -> Option C

5. Quick Check:

   Move left on match to find first occurrence [OK]

Hint: On match, search left side to find first occurrence [OK]

Common Mistakes:

• Returning immediately on first match
• Searching right side on match
• Ignoring duplicates in binary search