Binary Search Iterative Approach in DSA C#

Mental Model

Binary search finds a number by repeatedly cutting the search area in half until the number is found or no area remains.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if your word is before or after that page, and repeating this until you find the word.

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 the target number 9 using iterative binary search

Step 1: Set low to 0 and high to 7 (start and end of array)

low=0, high=7, array=[1,3,5,7,9,11,13,15]

Why: We start searching the whole array

Step 2: Calculate mid = (0 + 7) / 2 = 3, check array[mid] = 7

low=0, mid=3 (value=7), high=7

Why: Check middle element to decide which half to search next

Step 3: Since 7 < 9, move low to mid + 1 = 4

low=4, high=7

Why: Target must be in the right half

Step 4: Calculate mid = (4 + 7) / 2 = 5, check array[mid] = 11

low=4, mid=5 (value=11), high=7

Why: Check middle element of new search area

Step 5: Since 11 > 9, move high to mid - 1 = 4

low=4, high=4

Why: Target must be in the left half

Step 6: Calculate mid = (4 + 4) / 2 = 4, check array[mid] = 9

low=4, mid=4 (value=9), high=4

Why: Check the last possible element

Step 7: Found target at index 4, return 4

Index found: 4

Why: Target matches array[mid]

Result:

Final state: index 4 found with value 9

Annotated Code

DSA C#

using System;

class BinarySearch {
    public static int IterativeSearch(int[] arr, int target) {
        int low = 0;
        int high = arr.Length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // prevent overflow

            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
    }

    static void Main() {
        int[] array = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 9;
        int result = IterativeSearch(array, target);
        Console.WriteLine(result);
    }
}

while (low <= high) {

continue searching while search area is valid

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

calculate middle index safely

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

check if middle element is target

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

move low pointer to right half if target is greater

else { high = mid - 1; }

move high pointer to left half if target is smaller

Output

4

Complexity Analysis

Time: O(log n) because each step halves the search area until the target is found or area is empty

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 repeatedly

Edge Cases

empty array

returns -1 immediately since low > high

DSA C#

while (low <= high) {

target smaller than all elements

search narrows and returns -1 after checking all possibilities

DSA C#

while (low <= high) {

target larger than all elements

search narrows and returns -1 after checking all possibilities

DSA C#

while (low <= high) {

target is first element

found quickly when mid points to first element

DSA C#

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

target is last element

found quickly when mid points to last element

DSA C#

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

When to Use This Pattern

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

Common Mistakes

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

Mistake: Using while (low < high) which misses checking when low equals high
Fix: Use while (low <= high) to include all elements in search

Mistake: Not updating low or high correctly causing infinite loop
Fix: Update low to mid + 1 or high to mid - 1 depending on comparison

Summary

Finds the position of a target value in a sorted array by repeatedly dividing the search range.

Use when you have a sorted array and want to find an element efficiently.

The key insight is cutting the search space in half each step to quickly zero in on the target.

Practice

1. What is the main purpose of the Binary Search Iterative Approach in a sorted array?

easy

A. To find the maximum value in the array

B. To sort the array elements in ascending order

C. To reverse the array elements

D. To find the position of a target value efficiently by repeatedly dividing the search interval in half

Solution

1. Step 1: Understand binary search goal

   Binary search aims to find a target value's position quickly by checking the middle element and narrowing the search range.

2. Step 2: Identify iterative approach

   The iterative method uses a loop to repeatedly divide the search interval until the target is found or the interval is empty.

3. Final Answer:

   To find the position of a target value efficiently by repeatedly dividing the search interval in half -> Option D

4. Quick Check:

   Binary search = efficient target search [OK]

Hint: Binary search halves the search space each step [OK]

Common Mistakes:

• Confusing binary search with sorting
• Thinking it reverses the array
• Assuming it finds max value

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

easy

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

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

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

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

Solution

1. Step 1: Understand overflow risk

   Adding low and high directly can cause integer overflow if values are large.

2. Step 2: Use safe middle calculation

   Calculating mid as low + (high - low) / 2 avoids overflow by subtracting before adding.

3. Final Answer:

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

4. Quick Check:

   Safe mid calculation = low + (high - low) / 2 [OK]

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

Common Mistakes:

• Using (low + high) / 2 causing overflow
• Subtracting incorrectly in mid calculation
• Multiplying indices instead of adding

3. What will be the output of the following C# 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;
  }
}
Console.WriteLine(result);

medium

A. -1

B. 3

C. 2

D. 0

Solution

1. Step 1: Trace the binary search steps

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

2. Step 2: Output the result

   Since target found at index 2, Console.WriteLine prints 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Check middle element first to find target quickly [OK]

Common Mistakes:

• Confusing index with value
• Not updating low or high correctly
• Assuming target not found returns 0

4. Identify the error in the following 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. Change while condition to 'while (low <= high)'

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

C. Remove 'return -1;' at the end

D. Change 'low = mid + 1;' to 'low = mid - 1;'

Solution

1. Step 1: Analyze loop condition

   The loop uses 'while (low < high)', which misses checking when low equals high, possibly skipping the last element.

2. Step 2: Correct loop condition

   Changing to 'while (low <= high)' ensures all elements are checked including when low equals high.

3. Final Answer:

   Change while condition to 'while (low <= high)' -> Option A

4. Quick Check:

   Loop must include low == high to check all elements [OK]

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

Common Mistakes:

• Using < instead of <= in loop condition
• Incorrect mid calculation causing overflow
• Wrong update of low or high pointers

5. Given a sorted array with possible duplicate elements, how can you modify the iterative binary search to find the first occurrence of a target value?

hard

A. Return immediately when target is found

B. When target is found, continue searching left half to find earlier occurrence

C. Search only the right half after finding target

D. Use linear search instead of binary search

Solution

1. Step 1: Understand duplicates in sorted array

   Duplicates mean target can appear multiple times; we want the first index where it appears.

2. Step 2: Modify binary search to find first occurrence

   When target found at mid, record mid but continue searching left half (high = mid - 1) to find earlier occurrence.

3. Final Answer:

   When target is found, continue searching left half to find earlier occurrence -> Option B

4. Quick Check:

   Find first occurrence by searching left after match [OK]

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

Common Mistakes:

• Stopping search immediately on first match
• Searching right half after finding target
• Switching to linear search unnecessarily