Binary Search Iterative Approach in DSA Javascript - 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 not found return -1

Start with low and high pointers on the sorted array. Repeatedly check the middle element. If it matches target, return index. If middle is less, search right half. If more, search left half. Stop when low passes high.

Execution Sample

DSA Javascript

function binarySearch(arr, target) {
  let low = 0, 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 target in a sorted array using an iterative binary search.

Execution Table

Step	Operation	low	high	mid	arr[mid]	Comparison	Action	Visual State
1	Initialize pointers	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	[1, 3, 5, 7, 9, 11, 13]
4	Calculate mid	4	4	4	9	9 == 9?	Return 4	[1, 3, 5, 7, 9, 11, 13]

💡 Found target 9 at index 4, search ends.

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 target?

Because arr[mid] is smaller than target, the target must be in the right half, so we move low just after mid to avoid rechecking mid again. See execution_table row 2.

Why does the loop stop when low > high?

When low passes high, it means the search space is empty and target is not found. The loop condition low <= high ensures we only search valid parts. This is shown by the loop condition in the code and the exit condition.

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

To find the middle index between low and high, we average them and round down to get a valid array index. This is shown in each step of the execution_table where mid is calculated.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of mid at Step 3?

A 3

B 5

C 4

D 6

💡 Hint

Check the 'mid' column in execution_table row 3.

At which step does the condition low <= high become false, ending the loop?

A Step 4

B Step 3

C After Step 4 (loop exit)

D Step 2

💡 Hint

The loop ends after returning the target index at Step 4, so condition fails after that.

If the target was 12 instead of 9, what would happen to the 'high' pointer at Step 3?

A high would become 5

B high would become 6

C high would become 4

D high would not change

💡 Hint

At Step 3, arr[mid]=11 < 12, so low = mid + 1 and high does not change.

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
- Stop when low > high (target not found)

Full Transcript

Binary Search Iterative Approach starts with two pointers low and high at the start and end of a sorted array. We calculate the middle index mid and compare the middle element with the target. If they match, we return the mid index. If the middle element is less than the target, we move the low pointer to mid + 1 to search the right half. If it is greater, we move the high pointer to mid - 1 to search the left half. This process repeats until low passes high, meaning the target is not found. The code uses a while loop to perform this search efficiently in logarithmic time.