Binary Search Iterative Approach in DSA C++ - 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 using a fast search method.

🎯 Goal: Build a program that uses the iterative binary search method to find a book ID in a sorted list.

📋 What You'll Learn

Create a sorted array of integers representing book IDs

Set up variables to track the search range (start and end indices)

Implement the iterative binary search logic using a while loop

Print the index of the found book ID 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 a book in a library catalog or a product in an online store.

💼 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 values in order: 101, 203, 305, 407, 509, 611, 713

DSA C++

// Create the sorted array bookIDs with the given values
// Your code here

Hint

Use curly braces to list the numbers inside the array.

2

Set up the search range variables

Create two integer variables called start and end. Set start to 0 and end to 6 (the last index of bookIDs)

DSA C++

int bookIDs[] = {101, 203, 305, 407, 509, 611, 713};
// Create start and end variables for the search range
// Your code here

Hint

Remember the first index is 0 and the last index is the array length minus one.

3

Implement the iterative binary search logic

Write a while loop that runs while start is less than or equal to end. Inside the loop, calculate the middle index mid as (start + end) / 2. If bookIDs[mid] equals 509, break the loop. If bookIDs[mid] is less than 509, set start to mid + 1. Otherwise, set end to mid - 1. After the loop, create an integer variable result that is mid if bookIDs[mid] equals 509, else -1

DSA C++

int bookIDs[] = {101, 203, 305, 407, 509, 611, 713};
int start = 0;
int end = 6;
// Implement the iterative binary search for 509
// Your code here

Hint

Use a while loop and update start or end based on comparison with 509.

4

Print the search result

Write a std::cout statement to print the value of result followed by a newline

DSA C++

int bookIDs[] = {101, 203, 305, 407, 509, 611, 713};
int start = 0;
int end = 6;
int mid;
while (start <= end) {
    mid = (start + end) / 2;
    if (bookIDs[mid] == 509) {
        break;
    } else if (bookIDs[mid] < 509) {
        start = mid + 1;
    } else {
        end = mid - 1;
    }
}
int result = (bookIDs[mid] == 509) ? mid : -1;
// Print the result
// Your code here

Hint

Use std::cout << result << std::endl; to print the index.

Practice

1. What is the main purpose of the binarySearchIterative function in the iterative binary search approach?

easy

A. To find the position of a target value in a sorted array

B. To sort an unsorted array

C. To reverse the elements of an array

D. To count the number of elements in an array

Solution

1. Step 1: Understand the function goal

   The binary search function is designed to locate a target value within a sorted array efficiently.

2. Step 2: Identify the operation performed

   It repeatedly divides the search interval in half to find the target's position or determine it is not present.

3. Final Answer:

   To find the position of a target value in a sorted array -> Option A

4. Quick Check:

   Binary search locates target index [OK]

Hint: Binary search finds target index in sorted array fast [OK]

Common Mistakes:

• Thinking binary search sorts the array
• Confusing binary search with linear search
• Assuming it works on unsorted arrays

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

easy

A. int mid = (low - high) / 2;

B. int mid = (low + high) / 2;

C. int mid = low + (high - low) / 2;

D. int mid = (high - low) / 2 + high;

Solution

1. Step 1: Understand overflow risk in mid calculation

   Using (low + high) / 2 can overflow if low and high are large integers.

2. Step 2: Use safe formula to avoid overflow

   The formula low + (high - low) / 2 calculates mid without adding large numbers directly.

3. Final Answer:

   int mid = low + (high - low) / 2; -> Option C

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
• Subtracting incorrectly in mid calculation
• Mixing up low and high in formula

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

int arr[] = {2, 4, 6, 8, 10};
int n = 5;
int target = 6;
int result = binarySearchIterative(arr, n, target);
std::cout << result << std::endl;

// Assume binarySearchIterative is correctly implemented iterative binary search

medium

A. -1

B. 2

C. 3

D. 1

Solution

1. Step 1: Identify the target and array

   The array is {2, 4, 6, 8, 10} and the target is 6.

2. Step 2: Find the index of target using binary search

   6 is at index 2 (0-based indexing) in the array.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Index of 6 in array = 2 [OK]

Hint: Remember array indexing starts at 0 [OK]

Common Mistakes:

• Confusing index with value
• Using 1-based indexing instead of 0-based
• Assuming target not found returns 0

4. Identify the error in the following iterative binary search code snippet:

int binarySearchIterative(int arr[], int n, int target) {
    int low = 0, high = n - 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;
}

medium

A. The mid calculation can cause integer overflow

B. The loop condition should be low < high

C. The return value should be 0 when not found

D. The array should be unsorted for binary search

Solution

1. Step 1: Review mid calculation

   Mid is calculated as (low + high) / 2 which can overflow if low and high are large.

2. Step 2: Suggest safer mid calculation

   Use low + (high - low) / 2 to avoid overflow in mid calculation.

3. Final Answer:

   The mid calculation can cause integer overflow -> Option A

4. Quick Check:

   Mid calculation overflow risk = true [OK]

Hint: Use safe mid formula to avoid overflow [OK]

Common Mistakes:

• Changing loop condition incorrectly
• Returning 0 instead of -1 when not found
• Assuming binary search works on unsorted arrays

5. Given a sorted array arr = {1, 3, 5, 7, 9, 11, 13}, how many iterations will the iterative binary search take to find the target value 7?

hard

A. 4

B. 2

C. 3

D. 1

Solution

1. Step 1: Initialize low and high pointers

   low = 0, high = 6 (array length - 1)

2. Step 2: Trace each iteration to find 7

   Iteration 1: mid = 0 + (6-0)/2 = 3, arr[3] = 7 (target found at first check)

3. Step 3: Count iterations

   Only 1 iteration is needed because target is found immediately at mid index 3.

4. Final Answer:

   1 -> Option D

5. Quick Check:

   Target found at first mid check [OK]

Hint: Count mid calculations until target found [OK]

Common Mistakes:

• Assuming always 3 iterations for any search
• Counting array length instead of iterations
• Forgetting zero-based indexing