Binary Search Iterative Approach in DSA Java - 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

↓

Repeat loop or exit if low > high

↓

Return -1 if 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 Java

int binarySearch(int[] arr, int target) {
  int low = 0, high = arr.length - 1;
  while (low <= high) {
    int 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 < 10?	arr[mid] < target, low = mid + 1	[1, 3, 5, (7), 9, 11, 13]
3	Calculate mid	4	6	5	11	11 > 10?	arr[mid] > target, high = mid - 1	[1, 3, 5, 7, 9, (11), 13]
4	Calculate mid	4	4	4	9	9 < 10?	arr[mid] < target, low = mid + 1	[1, 3, 5, 7, (9), 11, 13]
5	Check condition	5	4	-	-	low > high?	Exit loop, target not found	[1, 3, 5, 7, 9, 11, 13]

💡 Loop ends when low (5) > high (4), meaning target 10 is not in array.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
low	0	4	4	5	5	5
high	6	6	4	4	4	4
mid	-	3	5	4	-	-
arr[mid]	-	7	11	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 to mid + 1 to search only the right side. See execution_table step 2 where low changes from 0 to 4.

Why does the loop stop when low becomes greater than high?

When low > high, it means the search range is empty and the target is not found. This is shown in execution_table step 5 where low=5 and high=4, so the loop ends.

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

Calculating mid this way finds the middle index of the current search range, splitting it in half to decide which side to search next. This is repeated in every loop iteration as shown in execution_table steps 2, 3, and 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, 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 execution_table row for step 3.

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

A Step 5

B Step 3

C Step 4

D Step 2

💡 Hint

Look at the 'Comparison' and 'Action' columns in execution_table step 5.

If the target was 7 instead of 10, at which step would the search find it?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at step 2 where arr[mid] equals 7 and the target is found.

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. In each step, it 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. The loop continues until low is greater than high, meaning the target is not found, and returns -1.

Practice

1. What is the main purpose of the mid variable in the iterative binary search algorithm?

easy

A. To find the middle index of the current search range

B. To store the target value to search

C. To keep track of the number of iterations

D. To hold the final result index

Solution

1. Step 1: Understand the role of mid in binary search

   The mid variable calculates the middle index between low and high pointers to split the search range.

2. Step 2: Purpose of mid

   It helps decide whether to search the left or right half by comparing the middle element with the target.

3. Final Answer:

   To find the middle index of the current search range -> Option A

4. Quick Check:

   mid = middle index [OK]

Hint: Mid splits search range to half each step [OK]

Common Mistakes:

• Confusing mid with target value
• Thinking mid counts iterations
• Assuming mid stores final answer

2. Which of the following is the correct way to calculate the middle index mid in an iterative binary search to avoid integer overflow?

easy

A. mid = low + (high - low) / 2

B. mid = (low + high) / 2

C. mid = (low - high) / 2

D. mid = (low * high) / 2

Solution

1. Step 1: Understand integer overflow risk

   Adding low and high directly can exceed integer limits if both are large.

2. Step 2: Safe calculation method

   Using low + (high - low) / 2 prevents overflow by subtracting before adding.

3. Final Answer:

   mid = low + (high - low) / 2 -> Option A

4. Quick Check:

   Safe mid calculation avoids overflow [OK]

Hint: Use low + (high - low)/2 to prevent overflow [OK]

Common Mistakes:

• Using (low + high)/2 causing overflow
• Using subtraction incorrectly
• Multiplying low and high

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

int[] arr = {2, 4, 6, 8, 10};
int target = 6;
int low = 0, high = arr.length - 1;
int result = -1;
while (low <= high) {
  int mid = low + (high - low) / 2;
  if (arr[mid] == target) {
    result = mid;
    break;
  } else if (arr[mid] < target) {
    low = mid + 1;
  } else {
    high = mid - 1;
  }
}
System.out.println(result);

medium

A. 4

B. 3

C. 2

D. -1

Solution

1. Step 1: Trace the binary search steps

   Initial low=0, high=4, mid=2. arr[2]=6 equals target 6, so result=2 and loop breaks.

2. Step 2: Output the result

   Result is 2, which is the index of target 6 in the array.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Index of 6 in arr = 2 [OK]

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

Common Mistakes:

• Confusing index with value
• Not breaking loop on match
• Incorrect mid calculation

4. Identify the error in this iterative binary search code snippet and choose the correct fix:

int binarySearch(int[] arr, int target) {
  int low = 0, high = arr.length - 1;
  while (low < high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

medium

A. Remove else if and use only if statements

B. Change mid calculation to (low + high) / 2

C. Return low instead of -1 at the end

D. Change while condition to low <= high

Solution

1. Step 1: Analyze loop condition

   The condition low < high misses the case when low equals high, possibly skipping the last element.

2. Step 2: Correct loop condition

   Changing to low <= high ensures the last element is checked.

3. Final Answer:

   Change while condition to low <= high -> Option D

4. Quick Check:

   Loop must include low == high [OK]

Hint: Use <= to include last element in search [OK]

Common Mistakes:

• Using < instead of <= in loop
• Incorrect mid calculation
• Returning wrong index on failure

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] == target, return mid immediately

B. When arr[mid] == target, update result and move high to mid - 1

C. When arr[mid] == target, move low to mid + 1

D. Ignore duplicates and return any matching index

Solution

1. Step 1: Understand duplicates in binary search

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

2. Step 2: Modify search to find first occurrence

   When arr[mid] == target, store mid as potential answer and continue searching left by setting high = mid - 1.

3. Final Answer:

   When arr[mid] == target, update result and move high to mid - 1 -> Option B

4. Quick Check:

   Move left on match to find first occurrence [OK]

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

Common Mistakes:

• Returning immediately on first match
• Moving right on match
• Ignoring duplicates