Binary Search Iterative Approach in DSA Go - Execution Trace

Concept Flow - Binary Search Iterative Approach

Start with sorted array and target

↓

Set low = 0, high = len-1

↓

While low <= high

↓

Calculate mid = (low + high) / 2

↓

Compare array[mid

↓

high=mid-1

↓

Repeat loop

↓

If not found, return -1

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 Go

func binarySearch(arr []int, target int) int {
  low, high := 0, len(arr)-1
  for low <= high {
    mid := (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 and returns the index or -1 if not found.

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?	arr[mid] < target, low = mid + 1	[1, 3, 5, (7), 9, 11, 13]
3	Update low	4	6	-	-	-	New range low=4, high=6	[9, 11, 13]
4	Calculate mid	4	6	5	11	11 > 9?	arr[mid] > target, high = mid - 1	[9, (11), 13]
5	Update high	4	4	-	-	-	New range low=4, high=4	[9]
6	Calculate mid	4	4	4	9	9 == 9?	Found target, return 4	[9]
7	End	4	4	4	9	Target found	Return index 4	[9]

💡 Target found at index 4, search ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
low	0	0	4	4	4	4	4
high	6	6	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 instead of mid when arr[mid] < target?

Because arr[mid] is less than target and already checked, so we exclude mid by setting low to mid + 1 (see Step 2 and 3 in execution_table).

Why does the loop stop when low > high?

Because the search range becomes empty, meaning target is not in the array. The condition low <= high ensures we only search valid ranges (see Step 7 exit).

Why do we calculate mid as (low + high) / 2 each iteration?

To check the middle element of the current search range and decide which half to search next (see Steps 2, 4, 6).

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the value of 'mid' and 'arr[mid]'?

A mid=4, arr[mid]=9

B mid=5, arr[mid]=11

C mid=3, arr[mid]=7

D mid=6, arr[mid]=13

💡 Hint

Check the 'mid' and 'arr[mid]' columns in row Step 4 of execution_table.

At which step does the condition low <= high become false, ending the loop if target was not found?

A After Step 7

B Step 7

C Step 6

D Step 3

💡 Hint

Look at the exit_note and understand the loop condition from concept_flow.

If the target was 14 (not in array), how would the 'low' and 'high' pointers change after Step 6?

A low would be 4, high would be 4

B low would be 0, high would be 6

C low would be 7, high would be 6

D low would be 5, high would be 4

💡 Hint

Think about how low moves when arr[mid] < target and when the search ends (see variable_tracker).

Concept Snapshot

Binary Search Iterative Approach:
- Works on sorted arrays
- Use two pointers: low and high
- Calculate mid = (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
- Return -1 if not found

Full Transcript

Binary Search Iterative Approach searches a sorted array by repeatedly dividing the search range in half. It starts with low at 0 and high at the last index. Each step calculates mid as the middle index. If the middle element equals the target, it returns the index. If the middle element is less than the target, it moves low to mid + 1 to search the right half. If greater, it moves high to mid - 1 to search the left half. This repeats until low exceeds high, meaning the target is not found. The execution table shows each step's low, high, mid, and comparison results, helping visualize how the search narrows down.