Binary Search Iterative Approach in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Binary Search Iterative Approach?

It repeatedly divides the sorted list in half to find the target value without using recursion, by moving the start or end pointers until the target is found or the search space is empty.

beginner

In Binary Search Iterative Approach, what happens if the middle element is less than the target?

The search continues in the right half of the list by moving the start pointer to middle + 1.

intermediate

Why is the Binary Search Iterative Approach more memory efficient than the recursive approach?

Because it does not use the call stack for recursion, it only uses variables to track the search range, saving memory.

beginner

What condition ends the loop in the Binary Search Iterative Approach?

The loop ends when the start pointer is greater than the end pointer, meaning the target is not in the list.

beginner

What is the time complexity of the Binary Search Iterative Approach and why?

O(log n) because the search space is halved in each iteration, quickly narrowing down the target position.

In the Binary Search Iterative Approach, what do you do if the middle element equals the target?

A Continue searching both halves

B Move start pointer to middle + 1

C Move end pointer to middle - 1

D Return the middle index

If the middle element matches the target, the search is successful and the middle index is returned.

What must be true about the list for Binary Search Iterative Approach to work correctly?

A The list must be empty

B The list must be unsorted

C The list must be sorted

D The list must contain only unique elements

Binary search requires the list to be sorted to correctly decide which half to search next.

Which variable tracks the start of the search range in Binary Search Iterative Approach?

A start

B mid

C end

D target

The 'start' variable marks the beginning index of the current search range.

How do you calculate the middle index in the Binary Search Iterative Approach to avoid overflow?

A (start + end) / 2

B start + (end - start) / 2

C end - (start / 2)

D start * end / 2

Using start + (end - start) / 2 prevents integer overflow when start and end are large.

What happens if the target is not found in the list after the loop ends?

A Return -1 or a value indicating not found

B Return 0

C Return the last middle index

D Throw an error

If the target is not found, the function returns -1 or a similar indicator to show absence.

Explain step-by-step how the Binary Search Iterative Approach finds a target in a sorted list.

Think about how the search space changes each step.

Describe the advantages of using an iterative approach for binary search compared to recursion.

Focus on memory and control flow differences.

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