Binary Search Iterative Approach in DSA Java

Mental Model

Binary search repeatedly cuts the list in half to find a target value quickly.

Analogy: Like guessing a number between 1 and 100 by always asking if the number is higher or lower than your guess, narrowing down the range each time.

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15]
Indices:  0      1      2      3      4       5       6       7
Pointers:  low ↑                             mid ↑                      high ↑

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13, 15], target: 9

Goal: Find the index of target 9 using iterative binary search

Step 1: Set low=0, high=7, calculate mid=(0+7)/2=3

Indices: 0 1 2 3 4 5 6 7
Array:  1 3 5 7 9 11 13 15
Pointers: low=0 ↑, mid=3 ↑ (value=7), high=7 ↑

Why: Start searching in the whole array, mid helps check middle value

Step 2: Compare target 9 with mid value 7; 9 > 7, so move low to mid+1=4

Indices: 0 1 2 3 4 5 6 7
Array:  1 3 5 7 9 11 13 15
Pointers: low=4 ↑, high=7 ↑

Why: Target is bigger, so ignore left half including mid

Step 3: Calculate new mid=(4+7)/2=5

Indices: 0 1 2 3 4 5 6 7
Array:  1 3 5 7 9 11 13 15
Pointers: low=4 ↑, mid=5 ↑ (value=11), high=7 ↑

Why: Check middle of new search range

Step 4: Compare target 9 with mid value 11; 9 < 11, so move high to mid-1=4

Indices: 0 1 2 3 4 5 6 7
Array:  1 3 5 7 9 11 13 15
Pointers: low=4 ↑, high=4 ↑

Why: Target is smaller, so ignore right half including mid

Step 5: Calculate new mid=(4+4)/2=4

Indices: 0 1 2 3 4 5 6 7
Array:  1 3 5 7 9 11 13 15
Pointers: low=4 ↑, mid=4 ↑ (value=9), high=4 ↑

Why: Check the only remaining element

Step 6: Compare target 9 with mid value 9; they are equal, return index 4

Indices: 0 1 2 3 4 5 6 7
Array:  1 3 5 7 9 11 13 15
Pointers: found target at index 4 ↑

Why: Target found, stop searching

Result:

Final state: target 9 found at index 4

Annotated Code

DSA Java

public class BinarySearchIterative {

    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // calculate middle index

            if (arr[mid] == target) {
                return mid; // target found
            } else if (arr[mid] < target) {
                low = mid + 1; // search right half
            } else {
                high = mid - 1; // search left half
            }
        }

        return -1; // target not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 9;
        int result = binarySearch(arr, target);

        if (result != -1) {
            System.out.println("Target " + target + " found at index " + result);
        } else {
            System.out.println("Target " + target + " not found in array");
        }
    }
}

int mid = low + (high - low) / 2; // calculate middle index

calculate middle index to split search range

if (arr[mid] == target) { return mid; }

check if middle element is the target

else if (arr[mid] < target) { low = mid + 1; }

target is greater, move low pointer to right half

else { high = mid - 1; }

target is smaller, move high pointer to left half

Output

Target 9 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search range

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted arrays by cutting search space in half each step

Edge Cases

empty array

returns -1 immediately because high < low

DSA Java

while (low <= high) {

target smaller than all elements

search narrows and returns -1 after no match

DSA Java

while (low <= high) {

target larger than all elements

search narrows and returns -1 after no match

DSA Java

while (low <= high) {

target is first element

found quickly when mid points to first index

DSA Java

if (arr[mid] == target) { return mid; }

target is last element

found quickly when mid points to last index

DSA Java

if (arr[mid] == target) { return mid; }

When to Use This Pattern

When you need to find an item quickly in a sorted list, use binary search iterative approach because it halves the search space each step.

Common Mistakes

Mistake: Calculating mid as (low + high) / 2 can cause integer overflow
Fix: Calculate mid as low + (high - low) / 2 to avoid overflow

Mistake: Not updating low or high correctly causing infinite loop
Fix: Ensure low = mid + 1 or high = mid - 1 to shrink search space

Mistake: Using while (low < high) instead of while (low <= high) misses last element
Fix: Use while (low <= high) to include all elements

Summary

It finds a target value in a sorted array by repeatedly dividing the search range in half.

Use it when you have a sorted list and want to find an element quickly.

The key insight is cutting the search space in half each step to find the target fast.

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