Why Binary Search and What Sorted Order Gives You in DSA C - Why It Works

Concept Flow - Why Binary Search and What Sorted Order Gives You

Start with sorted array

↓

Pick middle element

↓

Compare target with middle

↓

Search left

↓

Repeat until found or empty

↓

Result found or not

Binary search works on sorted arrays by repeatedly dividing the search range in half, comparing the target with the middle element, and choosing the left or right half accordingly until the target is found or the range is empty.

Execution Sample

DSA C

int binary_search(int arr[], int n, int target) {
  int left = 0, right = n - 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 'target' in a sorted array 'arr' using binary search and returns its index or -1 if not found.

Execution Table

Step	Operation	Left Index	Right Index	Mid Index	Mid Value	Comparison	Action	Array State
1	Initialize	0	6	-	-	-	Start search	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	7	7 == 9? No	7 < 9, move left to mid+1	[1, 3, 5, 7, 9, 11, 13]
3	Update left	4	6	-	-	-	Search right half	[1, 3, 5, 7, 9, 11, 13]
4	Calculate mid	4	6	5	11	11 == 9? No	11 > 9, move right to mid-1	[1, 3, 5, 7, 9, 11, 13]
5	Update right	4	4	-	-	-	Search left half	[1, 3, 5, 7, 9, 11, 13]
6	Calculate mid	4	4	4	9	9 == 9? Yes	Found target at index 4	[1, 3, 5, 7, 9, 11, 13]
7	End	4	4	4	9	-	Return index 4	[1, 3, 5, 7, 9, 11, 13]

💡 Target found at index 4, search ends

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
left	0	0	4	4	4	4	4
right	6	6	6	6	4	4	4
mid	-	3	-	5	-	4	4
mid_value	-	7	-	11	-	9	9

Key Moments - 3 Insights

Why must the array be sorted for binary search to work?

Because binary search decides which half to search next by comparing the target with the middle element. If the array is not sorted, this decision is invalid. See execution_table steps 2 and 4 where the comparison guides the search direction.

Why do we update 'left' to mid + 1 or 'right' to mid - 1 instead of just mid?

Because mid has already been checked and is not the target, so we exclude it from the next search range. This avoids infinite loops. See execution_table steps 3 and 5 where left and right are updated accordingly.

What happens if the target is not in the array?

The search range shrinks until left > right, meaning no elements left to check, and the function returns -1. This is not shown in this example but would stop the loop similarly to step 7.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'mid' at step 4?

A 3

B 5

C 4

D 6

💡 Hint

Check the 'Mid Index' column in execution_table row for step 4.

At which step does the search range narrow to a single element?

A Step 5

B Step 3

C Step 6

D Step 2

💡 Hint

Look at 'Left Index' and 'Right Index' columns to find when they become equal.

If the array was not sorted, what would happen to the binary search process?

A It would still find the target correctly.

B It would run faster.

C It might miss the target because comparisons are invalid.

D It would return the first element always.

💡 Hint

Refer to key_moments about why sorting is necessary.

Concept Snapshot

Binary Search requires a sorted array.
Pick middle element, compare with target.
If equal, return index.
If target > mid, search right half.
If target < mid, search left half.
Repeat until found or range empty.

Full Transcript

Binary search is a fast way to find an item in a sorted list. It works by repeatedly picking the middle element and comparing it to the target. If the middle element is the target, the search ends. If the target is bigger, the search continues in the right half. If smaller, it continues in the left half. This process repeats until the target is found or the search range is empty. The array must be sorted for this to work because the decision to go left or right depends on order. The code example shows how left, right, and mid pointers move to narrow down the search. If the target is not found, the function returns -1.

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