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, and so on until you find it.

Sorted array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> null
                 ↑
             start middle end

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: Check middle element at index 3 (value 7)

[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
                 ↑ middle
start=0 end=6

Why: We start by looking at the middle to decide which half to search next

Step 2: Since 9 > 7, move start to index 4

[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
                         ↑ middle
start=4 end=6

Why: We ignore the left half because 9 must be in the right half

Step 3: Check middle element at index 5 (value 11)

[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
                         ↑ middle
start=4 end=6

Why: We look at the middle of the new search range

Step 4: Since 9 < 11, move end to index 4

[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
                     ↑ middle
start=4 end=4

Why: We ignore the right half because 9 must be in the left half

Step 5: Check middle element at index 4 (value 9)

[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
                     ↑ middle
start=4 end=4

Why: We found the element we are searching for

Result:

Final state: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
                     ↑ found 9 at index 4

Annotated Code

DSA C

#include <stdio.h>

int binary_search(int arr[], int size, int target) {
    int start = 0;
    int end = size - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;  // find middle index
        if (arr[mid] == target) {
            return mid;  // found target
        } else if (arr[mid] < target) {
            start = mid + 1;  // search right half
        } else {
            end = mid - 1;  // search left half
        }
    }
    return -1;  // target not found
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 9;
    int index = binary_search(arr, size, target);
    if (index != -1) {
        printf("Found %d at index %d\n", target, index);
    } else {
        printf("%d not found in array\n", target);
    }
    return 0;
}

int mid = start + (end - start) / 2; // find middle index

calculate middle index to split search range

if (arr[mid] == target) {

check if middle element is the target

start = mid + 1; // search right half

move start to right half if target is greater

end = mid - 1; // search left half

move end to left half if target is smaller

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: Compared to linear search O(n), binary search is much faster on sorted data because it skips half the elements each time

Edge Cases

empty array

returns -1 immediately since start > end

DSA C

while (start <= end) {

target smaller than all elements

search narrows and returns -1 after checking all halves

DSA C

while (start <= end) {

target larger than all elements

search narrows and returns -1 after checking all halves

DSA C

while (start <= end) {

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 area in half each time, making it very fast.

Common Mistakes

Mistake: Not checking if the array is sorted before using binary search
Fix: Always ensure the array is sorted before applying binary search

Mistake: Calculating middle index as (start + end) / 2 which can overflow
Fix: Calculate middle as start + (end - start) / 2 to avoid overflow

Mistake: Using binary search on unsorted data leading to wrong results
Fix: Sort the data first or use linear search if data is unsorted

Summary

Binary search finds a target value quickly by repeatedly dividing the search range in half.

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

The key insight is that sorted order lets you ignore half the data 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 search in lists with odd number of elements

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

C. Because binary search divides the list and compares middle elements to find the target efficiently

D. Because binary search requires the list to be reversed

Solution

1. Step 1: Understand binary search working

   Binary search works by repeatedly dividing the sorted list and comparing the middle element to the target value.

2. Step 2: Importance of sorted order

   Sorted order allows us to decide which half to discard after each comparison, making search efficient.

3. Final Answer:

   Because binary search divides the list and compares middle elements to find the target efficiently -> Option C

4. Quick Check:

   Sorted list needed for binary search = Because it divides and compares middle elements [OK]

Hint: Binary search needs sorted list to halve search space fast [OK]

Common Mistakes:

• Thinking binary search works on unsorted lists
• Assuming binary search needs duplicates
• Believing binary search requires odd length lists

2. Which of the following is the correct syntax to start a binary search loop in C for an array arr of size n?

easy

A. int low = 1, high = n - 1; while (low <= high) { ... }

B. int low = 0, high = n - 1; while (low <= high) { ... }

C. int low = 0, high = n; while (low < high) { ... }

D. int low = 1, high = n; while (low < high) { ... }

Solution

1. Step 1: Identify correct index range for array

   Array indices in C start at 0 and end at n-1, so low = 0 and high = n-1.

2. Step 2: Correct loop condition for binary search

   Loop continues while low is less than or equal to high to cover all elements.

3. Final Answer:

   int low = 0, high = n - 1; while (low <= high) { ... } -> Option B

4. Quick Check:

   Array indices 0 to n-1 and loop while low <= high [OK]

Hint: Array indices start at 0; loop while low ≤ high [OK]

Common Mistakes:

• Starting low at 1 instead of 0
• Using high = n instead of n-1
• Using < instead of <= in loop condition

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

int arr[] = {2, 4, 6, 8, 10};
int low = 0, high = 4, mid;
int target = 6;
while (low <= high) {
  mid = (low + high) / 2;
  if (arr[mid] == target) {
    printf("Found at index %d", mid);
    break;
  } else if (arr[mid] < target) {
    low = mid + 1;
  } else {
    high = mid - 1;
  }
}

medium

A. Found at index 1

B. Found at index 3

C. Not found

D. Found at index 2

Solution

1. Step 1: Initialize variables and first mid calculation

   low=0, high=4, mid=(0+4)/2=2; arr[2]=6 matches target 6.

2. Step 2: Check condition and print result

   Since arr[mid] == target, print "Found at index 2" and break loop.

3. Final Answer:

   Found at index 2 -> Option D

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Calculate mid as (low+high)/2 and compare to target [OK]

Common Mistakes:

• Calculating mid incorrectly
• Off-by-one errors in index
• Printing wrong index

4. Identify the error in this binary search code snippet and choose the correct fix:

int arr[] = {1, 3, 5, 7, 9};
int low = 0, high = 5, mid;
int target = 7;
while (low <= high) {
  mid = (low + high) / 2;
  if (arr[mid] == target) {
    printf("Found at %d", mid);
    break;
  } else if (arr[mid] < target) {
    low = mid + 1;
  } else {
    high = mid - 1;
  }
}

medium

A. Change high to 4 instead of 5

B. Change low to 1 instead of 0

C. Change mid calculation to mid = (low - high) / 2

D. No error, code is correct

Solution

1. Step 1: Check array index bounds

   Array size is 5, so highest index is 4. Setting high=5 causes out-of-bounds access.

2. Step 2: Fix high initialization

   Set high = 4 to stay within valid indices and avoid runtime errors.

3. Final Answer:

   Change high to 4 instead of 5 -> Option A

4. Quick Check:

   Array indices 0 to 4, high must be 4 [OK]

Hint: High index must be last valid index (size-1) [OK]

Common Mistakes:

• Setting high to array size instead of size-1
• Changing low incorrectly
• Incorrect mid calculation

5. Given a sorted array arr = {1, 3, 5, 7, 9, 11, 13}, you want to find the smallest element greater than or equal to 8 using binary search. Which approach correctly finds this element?

hard

A. Modify binary search to move high = mid - 1 when arr[mid] >= 8, else low = mid + 1

B. Use normal binary search to find 8 directly; if not found, return -1

C. Sort the array again before binary search

D. Use linear search instead of binary search

Solution

1. Step 1: Understand the problem

   We want the smallest element >= 8, which may not be exactly 8 in the array.

2. Step 2: Modify binary search for lower bound

   When arr[mid] >= 8, move high to mid - 1 to find smaller candidates; else move low to mid + 1.

3. Step 3: After loop, low points to smallest element >= 8

   This approach finds the correct element (9 at index 4).

4. Final Answer:

   Modify binary search to move high = mid - 1 when arr[mid] >= 8, else low = mid + 1 -> Option A

5. Quick Check:

   Lower bound binary search finds smallest element ≥ target [OK]

Hint: Adjust binary search to find lower bound by moving high on >= [OK]

Common Mistakes:

• Using normal binary search without modification
• Sorting array again unnecessarily
• Choosing linear search over binary search