Binary Search as Divide and Conquer in DSA C# - Build from Scratch

Binary Search as Divide and Conquer

📖 Scenario: You are helping a librarian find a book quickly in a sorted list of book IDs. Instead of checking each book one by one, you will use a smart method called binary search that splits the list in half each time to find the book faster.

🎯 Goal: Build a program that uses binary search to find the position of a given book ID in a sorted list of book IDs.

📋 What You'll Learn

Create a sorted array of integers representing book IDs

Create a variable for the book ID to search for

Implement the binary search logic using divide and conquer

Print the index of the found book ID or -1 if not found

💡 Why This Matters

🌍 Real World

Binary search is used in many real-world applications like searching in phone contacts, dictionaries, or any sorted data to find information quickly.

💼 Career

Understanding binary search is essential for software developers and data scientists to optimize search operations and improve program efficiency.

1

Create the sorted array of book IDs

Create an integer array called bookIds with these exact values: 101, 203, 305, 407, 509, 611, 713.

DSA C#

// Create the sorted array of book IDs
// Your code here

Hint

Use int[] bookIds = { ... }; to create the array with the exact numbers.

2

Set the book ID to search for

Create an integer variable called targetId and set it to 407.

DSA C#

int[] bookIds = {101, 203, 305, 407, 509, 611, 713};
// Create the target book ID to search for
// Your code here

Hint

Use int targetId = 407; to set the book ID you want to find.

3

Implement binary search logic

Write a method called BinarySearch that takes int[] bookIds and int targetId as parameters and returns the index of targetId using binary search. Use variables left, right, and mid inside a while loop to divide and conquer the search.

DSA C#

int[] bookIds = {101, 203, 305, 407, 509, 611, 713};
int targetId = 407;

// Write the BinarySearch method below
// Your code here

Hint

Use a while loop with left and right pointers. Calculate mid and compare bookIds[mid] with targetId. Adjust left or right accordingly.

4

Print the search result

Call the BinarySearch method with bookIds and targetId, store the result in index, and print index.

DSA C#

int[] bookIds = {101, 203, 305, 407, 509, 611, 713};
int targetId = 407;

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

// Call BinarySearch and print the result
// Your code here

Hint

Call BinarySearch(bookIds, targetId), save the result in index, then print index using Console.WriteLine(index);.

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