Binary Search as Divide and Conquer in DSA C#

Mental Model

Binary search splits a sorted list into halves to quickly find a target value by ignoring half the list each time.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if the word is in the first or second half, and repeating this until you find it.

Sorted array: [1, 3, 5, 7, 9, 11, 13]
Indices:     [0, 1, 2, 3, 4,  5,  6]
Pointers:    low ↑           mid ↑           high ↑

Dry Run Walkthrough

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

Goal: Find the index of the target value 9 in the sorted array using binary search.

Step 1: Calculate mid index between low=0 and high=6; mid=3; check value at mid=7

[1, 3, 5, 7, 9, 11, 13]
Indices: 0  1  2  3  4  5  6
Pointers: low=0 ↑ mid=3 ↑ high=6 ↑

Why: We start by checking the middle element to decide which half to search next.

Step 2: Since 7 < 9, move low pointer to mid+1=4 to search right half

[1, 3, 5, 7, 9, 11, 13]
Indices: 0  1  2  3  4  5  6
Pointers: low=4 ↑       mid=3    high=6 ↑

Why: Target is greater than mid value, so ignore left half including mid.

Step 3: Calculate new mid between low=4 and high=6; mid=5; check value at mid=11

[1, 3, 5, 7, 9, 11, 13]
Indices: 0  1  2  3  4  5  6
Pointers: low=4 ↑ mid=5 ↑ high=6 ↑

Why: Check middle of the new search range to narrow down further.

Step 4: Since 11 > 9, move high pointer to mid-1=4 to search left half

[1, 3, 5, 7, 9, 11, 13]
Indices: 0  1  2  3  4  5  6
Pointers: low=4 ↑       mid=5    high=4 ↑

Why: Target is less than mid value, so ignore right half including mid.

Step 5: Calculate new mid between low=4 and high=4; mid=4; check value at mid=9

[1, 3, 5, 7, 9, 11, 13]
Indices: 0  1  2  3  4  5  6
Pointers: low=4 ↑ mid=4 ↑ high=4 ↑

Why: Only one element left to check, which might be the target.

Step 6: Value at mid equals target 9; return index 4

[1, 3, 5, 7, 9, 11, 13]
Indices: 0  1  2  3  4  5  6
Pointers: low=4 ↑ mid=4 ↑ high=4 ↑

Why: Target found at mid index.

Result:

Final state: [1, 3, 5, 7, 9, 11, 13]
Target 9 found at index 4

Annotated Code

DSA C#

using System;

class BinarySearch {
    // Binary search function using divide and conquer
    public static int Search(int[] arr, int target) {
        int low = 0;
        int high = arr.Length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // find 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
    }

    static void Main() {
        int[] array = {1, 3, 5, 7, 9, 11, 13};
        int target = 9;
        int index = Search(array, target);
        if (index != -1) {
            Console.WriteLine($"Target {target} found at index {index}");
        } else {
            Console.WriteLine($"Target {target} not found in array");
        }
    }
}

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

Calculate middle index to split the search range.

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

Check if middle element is the target; if yes, return index.

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

If target is greater, move low pointer to right half.

else { high = mid - 1; }

If 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 space, quickly narrowing down the target.

Space: O(1) because it uses only a few variables and no extra space proportional to input size.

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted arrays by dividing the problem in half each time.

Edge Cases

Empty array

Returns -1 immediately since low > high at start.

DSA C#

while (low <= high)

Target not in array

Search narrows until low > high, then returns -1.

DSA C#

while (low <= high)

Single element array with target present

Checks single element and returns index if matches.

DSA C#

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

When to Use This Pattern

When you need to find an item quickly in a sorted list, look for binary search because it divides the search space in half each step, making it very efficient.

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 loops.
Fix: Ensure low = mid + 1 when target is greater, and high = mid - 1 when target is smaller.

Summary

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

Use it when you have a sorted list and want fast search performance.

The key insight is to ignore half the list each time based on comparison with the middle element.

Practice

1. What is the main idea behind Binary Search as a divide and conquer algorithm?

easy

A. It repeatedly divides the search interval in half to find the target value.

B. It checks every element one by one until it finds the target.

C. It sorts the array before searching for the target.

D. It uses a queue to store elements during the search.

Solution

1. Step 1: Understand divide and conquer in binary search

   Binary search splits the array into two halves and decides which half to search next.

2. Step 2: Identify the repeated halving process

   It keeps dividing the search space by half until the target is found or no elements remain.

3. Final Answer:

   It repeatedly divides the search interval in half to find the target value. -> Option A

4. Quick Check:

   Divide and conquer = repeated halving [OK]

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

Common Mistakes:

• Thinking binary search checks every element
• Confusing binary search with linear search
• Assuming binary search sorts the array

2. Which of the following is the correct C# syntax to calculate the middle index in 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 = (low * high) / 2;

Solution

1. Step 1: Understand overflow risk in mid calculation

   Adding low and high directly can overflow if both are large.

2. Step 2: Use safe formula to avoid overflow

   Calculating mid as low + (high - low) / 2 prevents overflow by subtracting first.

3. Final Answer:

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

4. Quick Check:

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

Hint: Use low + (high - low) / 2 to avoid 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. 3

B. 2

C. -1

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 B

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Check mid index value first to find target quickly [OK]

Common Mistakes:

• Confusing index with value
• Not updating low and high correctly
• Assuming target not found and returning -1

4. Identify the bug in this binary search code snippet and select 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. Return 'low' instead of '-1' when target not found.

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

C. Remove 'else' before 'high = mid - 1;' to fix logic.

D. Change while condition to 'low <= high' to include last element.

Solution

1. Step 1: Analyze the loop condition

   The condition 'low < high' misses checking when low equals high, possibly skipping last element.

2. Step 2: Fix loop to include all elements

   Changing condition to 'low <= high' ensures the last element is checked.

3. Final Answer:

   Change while condition to 'low <= high' to include last element. -> Option D

4. Quick Check:

   Loop condition must cover all indices [OK]

Hint: Use 'low <= high' to cover full search range [OK]

Common Mistakes:

• Using 'low < high' and missing last element
• Changing mid calculation unnecessarily
• Returning wrong index when not found

5. You have a sorted array with duplicate values: int[] arr = {1, 2, 2, 2, 3, 4}. How would you modify binary search to find the first occurrence of 2?

hard

A. After finding target, continue searching left half to find first occurrence.

B. Return the first found index immediately without further checks.

C. Search the right half after finding target to find last occurrence.

D. Use linear search instead of binary search for duplicates.

Solution

1. Step 1: Understand duplicates in binary search

   Standard binary search returns any occurrence, not necessarily the first.

2. Step 2: Modify search to find first occurrence

   When target found, move high pointer to mid - 1 to check left side for earlier occurrence, keep track of current mid.

3. Final Answer:

   After finding target, continue searching left half to find first occurrence. -> Option A

4. Quick Check:

   Find first occurrence by searching left after match [OK]

Hint: Keep searching left half after finding target for first occurrence [OK]

Common Mistakes:

• Stopping at first found index ignoring duplicates
• Searching right half instead of left for first occurrence
• Using linear search unnecessarily