Binary Search Iterative Approach in DSA Java - Build from Scratch

Binary Search Iterative Approach

📖 Scenario: You have a sorted list of book IDs in a library system. You want to quickly find if a specific book ID exists in the list using a fast search method.

🎯 Goal: Build a Java program that uses the iterative binary search method to find a target book ID in a sorted array of book IDs.

📋 What You'll Learn

Create an integer array called bookIDs with sorted values

Create an integer variable called targetID to hold the book ID to search

Implement an iterative binary search using a while loop with variables left, right, and mid

Print the index of the targetID if found, or -1 if not found

💡 Why This Matters

🌍 Real World

Binary search is used in many software systems to quickly find data in sorted lists, such as searching for user IDs, product codes, or book IDs in libraries.

💼 Career

Understanding binary search is essential for software developers and engineers to write efficient search algorithms and optimize performance in applications.

1

Create the sorted array of book IDs

Create an integer array called bookIDs with these exact sorted values: 101, 203, 305, 407, 509.

DSA Java

// Your code here

Hint

Use curly braces {} to list the array values separated by commas.

2

Set the target book ID to search

Create an integer variable called targetID and set it to 305.

DSA Java

int[] bookIDs = {101, 203, 305, 407, 509};
// Your code here

Hint

Use int targetID = 305; to create the variable.

3

Implement the iterative binary search

Write a while loop using variables left, right, and mid to perform iterative binary search on bookIDs to find targetID. Store the found index in an integer variable called result. If not found, set result to -1.

DSA Java

int[] bookIDs = {101, 203, 305, 407, 509};
int targetID = 305;
// Your code here

Hint

Use a while loop that runs while left <= right. Calculate mid as shown. Compare bookIDs[mid] with targetID to decide how to move left and right.

4

Print the search result

Print the value of the integer variable result.

DSA Java

int[] bookIDs = {101, 203, 305, 407, 509};
int targetID = 305;

int left = 0;
int right = bookIDs.length - 1;
int result = -1;

while (left <= right) {
    int mid = left + (right - left) / 2;
    if (bookIDs[mid] == targetID) {
        result = mid;
        break;
    } else if (bookIDs[mid] < targetID) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
// Your code here

Hint

Use System.out.println(result); to print the index.

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