Why Binary Search and What Sorted Order Gives You in DSA C# - Why This Pattern

Mental Model

Binary search quickly finds a value by repeatedly cutting the search area in half, but it only works if the list is sorted.

Analogy: Imagine looking for a word in a dictionary: you open near the middle, decide if your word is before or after, then open the middle of that half, repeating until you find it.

Sorted array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> null
Search range: ↑ start at full array
Pointers: low -> mid -> high

Dry Run Walkthrough

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

Goal: Find the position of 9 quickly using binary search

Step 1: Calculate mid index between low=0 and high=6 -> mid=3, check value 7

[1] -> [3] -> [5] -> [7↑] -> [9] -> [11] -> [13] -> null

Why: We check middle to decide which half to search next

Step 2: 9 > 7, so move low to mid+1=4

Search range narrowed: [9↑] -> [11] -> [13] -> null

Why: Since 9 is greater, we ignore left half including 7

Step 3: Calculate mid between low=4 and high=6 -> mid=5, check value 11

[9] -> [11↑] -> [13] -> null

Why: Check middle of new range to narrow search

Step 4: 9 < 11, so move high to mid-1=4

Search range narrowed: [9↑] -> null

Why: Since 9 is less, ignore right half including 11

Step 5: Calculate mid between low=4 and high=4 -> mid=4, check value 9

[9↑] -> null

Why: Only one element left, check if it matches

Step 6: Found 9 at index 4

[9↑] -> null

Why: Search successful, return index

Result:

Final state: [9↑] -> null
Answer: Found 9 at index 4

Annotated Code

DSA C#

using System;

class BinarySearchDemo
{
    // Binary search function returns index or -1 if not found
    public static int BinarySearch(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; // found target

            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[] sortedArray = {1, 3, 5, 7, 9, 11, 13};
        int target = 9;

        int index = BinarySearch(sortedArray, target);

        if (index != -1)
            Console.WriteLine($"Found {target} at index {index}");
        else
            Console.WriteLine($"{target} not found in array");
    }
}

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

Calculate middle index to split search range

if (arr[mid] == target) return mid; // found target

Check if middle element is the target

if (arr[mid] < target) low = mid + 1; // search right half

If target is greater, move low pointer to right half

else high = mid - 1; // search left half

If target is smaller, move high pointer to left half

Output

Found 9 at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Linear search takes O(n) time by checking each element one by one, which is slower for large sorted lists

Edge Cases

Empty array

Returns -1 immediately since low > high

DSA C#

while (low <= high)

Target smaller than all elements

Search narrows to empty range and returns -1

DSA C#

while (low <= high)

Target larger than all elements

Search narrows to empty range and returns -1

DSA C#

while (low <= high)

When to Use This Pattern

When you need to find an item quickly in a sorted list, use binary search because it cuts the search space in half each time, making it very fast.

Common Mistakes

Mistake: Not ensuring the array is sorted before binary search
Fix: Always sort the array first or confirm it is sorted before applying binary search

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

Mistake: Using low < high instead of low <= high in loop condition
Fix: Use low <= high to include the case when low equals high

Summary

Binary search finds an element quickly by repeatedly dividing the search range in half.

Use binary search when you have a sorted list and want fast lookup.

The key insight is that sorted order lets you ignore half the list each step, making search much faster.

Practice

1. Why is it important for a list to be sorted before applying binary search?

easy

A. Because binary search can only find the first element in any list

B. Because binary search works only on lists with unique elements

C. Because binary search divides the list and compares values assuming order

D. Because binary search requires the list to be reversed

Solution

1. Step 1: Understand binary search working principle

   Binary search splits the list into halves and compares the middle element to the target, assuming the list is sorted.

2. Step 2: Importance of sorted order

   If the list is not sorted, the halves cannot be correctly chosen, so binary search fails to find the target efficiently.

3. Final Answer:

   Because binary search divides the list and compares values assuming order -> Option C

4. Quick Check:

   Sorted list needed for binary search = True [OK]

Hint: Binary search needs order to split search space correctly [OK]

Common Mistakes:

• Thinking binary search works on unsorted lists
• Assuming binary search finds duplicates only
• Confusing binary search with linear search

2. Which of the following is the correct syntax to start a binary search on a sorted array named arr in C#?

easy

A. int index = Array.BinarySearch(arr, target);

B. int index = arr.BinarySearch(target);

C. int index = BinarySearch(arr, target);

D. int index = arr.SearchBinary(target);

Solution

1. Step 1: Recall C# binary search method usage

   C# provides a static method Array.BinarySearch that takes the array and the target value.

2. Step 2: Check method call correctness

   int index = Array.BinarySearch(arr, target); correctly calls Array.BinarySearch(arr, target). Other options use invalid syntax or methods.

3. Final Answer:

   int index = Array.BinarySearch(arr, target); -> Option A

4. Quick Check:

   Correct C# binary search syntax = int index = Array.BinarySearch(arr, target); [OK]

Hint: Use Array.BinarySearch for arrays in C# [OK]

Common Mistakes:

• Trying to call BinarySearch as instance method on array
• Using wrong method names like SearchBinary
• Missing the Array class prefix

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

int[] arr = {2, 4, 6, 8, 10};
int index = Array.BinarySearch(arr, 6);
Console.WriteLine(index);

medium

A. -1

B. 2

C. 3

D. 0

Solution

1. Step 1: Understand array and target

   The array is sorted: [2, 4, 6, 8, 10]. The target is 6.

2. Step 2: Find index of target in array

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

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Index of 6 in array = 2 [OK]

Hint: BinarySearch returns index of found element [OK]

Common Mistakes:

• Confusing index with value
• Assuming 1-based indexing
• Expecting -1 when element is present

4. The following code tries to find the index of 5 in a sorted array but gives an unexpected result. What is the error?

int[] arr = {1, 3, 7, 9, 11};
int index = Array.BinarySearch(arr, 5);
Console.WriteLine(index);

medium

A. 5 is not in the array, so negative index is returned

B. The method call syntax is incorrect

C. BinarySearch cannot be used on integers

D. The array is not sorted

Solution

1. Step 1: Check if array is sorted

   The array [1, 3, 7, 9, 11] is sorted in ascending order.

2. Step 2: Understand BinarySearch return when element not found

   When the target (5) is not found, BinarySearch returns a negative number indicating the bitwise complement of the insertion point.

3. Final Answer:

   5 is not in the array, so negative index is returned -> Option A

4. Quick Check:

   Not found element returns negative index [OK]

Hint: Negative result means element not found [OK]

Common Mistakes:

• Thinking array is unsorted
• Expecting -1 always when not found
• Believing syntax is wrong

5. You have a sorted list of student scores: int[] scores = {55, 67, 78, 89, 92, 95}. You want to find if a score of 80 exists using binary search. If not found, you want to insert 80 in the correct position to keep the list sorted. Which approach correctly achieves this?

hard

A. Sort the array after inserting 80 at the end

B. Use Array.BinarySearch and insert at returned index directly

C. Use linear search to find 80 and insert if missing

D. Use Array.BinarySearch to find 80; if negative, insert at ~index returned

Solution

1. Step 1: Use Array.BinarySearch to find 80

   BinarySearch returns index if found; if not found, returns negative number which is bitwise complement of insertion point.

2. Step 2: Insert 80 at correct position

   If result is negative, invert bits (~index) to get insertion position to keep array sorted.

3. Final Answer:

   Use Array.BinarySearch to find 80; if negative, insert at ~index returned -> Option D

4. Quick Check:

   Negative index means insert at bitwise complement [OK]

Hint: Insert at ~index if BinarySearch returns negative [OK]

Common Mistakes:

• Inserting at negative index directly
• Not using binary search result properly
• Sorting after insertion instead of correct position