Binary Search Iterative Approach in DSA Typescript - Execution Trace

Concept Flow - Binary Search Iterative Approach

Start with sorted array and target

↓

Set low = 0, high = array.length - 1

↓

While low <= high

↓

Calculate mid = (low + high) // 2

↓

Compare array[mid

↓

Equal

↓

Return mid

↓

Repeat loop

↓

If low > high

↓

Return -1 (not found)

This flow shows how binary search narrows down the search range by adjusting low and high pointers until the target is found or the range is empty.

Execution Sample

DSA Typescript

function binarySearch(arr: number[], target: number): number {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    let 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;
}

This code searches for a target number in a sorted array using an iterative binary search.

Execution Table

Step	Operation	low	high	mid	arr[mid]	Comparison	Action	Search Range Visual
1	Initialize low and high	0	6	-	-	-	Start search	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	7	7 < 9	low = mid + 1 = 4	[1, 3, 5, 7, 9, 11, 13]
3	Calculate mid	4	6	5	11	11 > 9	high = mid - 1 = 4	[9, 11, 13]
4	Calculate mid	4	4	4	9	9 == 9	Return mid = 4	[9]
5	Exit	4	4	4	9	Found target	Stop search	[9]

💡 Search ends when target is found at index 4 or when low > high (not in this case).

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
low	0	4	4	4	4
high	6	6	4	4	4
mid	-	3	5	4	4
arr[mid]	-	7	11	9	9

Key Moments - 3 Insights

Why do we update low to mid + 1 when arr[mid] is less than the target?

Because arr[mid] is smaller than the target, the target must be in the right half, so we move low just after mid to exclude mid from the search (see Step 2 in execution_table).

Why do we stop the search when low becomes greater than high?

When low > high, it means the search range is empty and the target is not in the array (not shown in this example but explained in exit_note).

Why do we calculate mid as Math.floor((low + high) / 2)?

To find the middle index between low and high, rounding down to avoid fractional index (see Steps 2-4 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the value of high after the action?

A 6

B 4

C 5

D 3

💡 Hint

Check the 'Action' column at Step 3 where high is updated to mid - 1.

At which step does the condition arr[mid] == target become true?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Comparison' column to find when arr[mid] equals the target.

If the target was 12 instead of 9, what would happen to the value of low after Step 2?

A low would become 4

B low would become 5

C low would become 6

D low would remain 0

💡 Hint

Check how low changes when arr[mid] < target in Step 2.

Concept Snapshot

Binary Search Iterative Approach:
- Works on sorted arrays
- Use two pointers: low and high
- Calculate mid = floor((low + high)/2)
- Compare arr[mid] with target
- If equal, return mid
- If arr[mid] < target, move low to mid + 1
- Else, move high to mid - 1
- Repeat until low > high (target not found)

Full Transcript

Binary search is a method to find a target value in a sorted array by repeatedly dividing the search range in half. We start with two pointers: low at the start and high at the end of the array. We calculate the middle index mid and compare the value at mid with the target. If they match, we return mid as the found index. If the value at mid is less than the target, we move low to mid + 1 to search the right half. If it is greater, we move high to mid - 1 to search the left half. This process repeats until low is greater than high, which means the target is not in the array. The execution table shows each step with the current low, high, mid, and the action taken, helping visualize how the search narrows down.