Binary Search as Divide and Conquer in DSA C# - Time & Space Complexity

Time Complexity: Binary Search as Divide and Conquer

O(log n)

Understanding Time Complexity

We want to understand how the time taken by binary search changes as the list size grows.

How does splitting the search area in half affect the number of steps?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int BinarySearch(int[] arr, int target) {
    int left = 0, right = arr.Length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
    

This code searches for a target number in a sorted array by repeatedly dividing the search range in half.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking the middle element and adjusting the search range.
• How many times: The search range halves each time until the target is found or range is empty.

How Execution Grows With Input

Each step cuts the search area in half, so the number of steps grows slowly as the list grows.

Input Size (n)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: Doubling the input size adds only one extra step.

Final Time Complexity

Time Complexity: O(log n)

This means the time grows slowly, adding just one step each time the input size doubles.

Common Mistake

[X] Wrong: "Binary search checks every element like linear search."

[OK] Correct: Binary search skips half the elements each step, so it does far fewer checks.

Interview Connect

Understanding binary search time complexity shows you can analyze efficient algorithms that use smart dividing steps.

Self-Check

"What if the array was not sorted? How would the time complexity change?"

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