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

↓

Set low = 0, high = length-1

↓

Calculate mid = (low + high) / 2

↓

Compare target with array[mid

↓

high=mid-1

↓

Repeat until low > high

↓

Target not found

Binary search repeatedly divides a sorted array to find a target quickly by comparing the middle element and narrowing the search range.

Execution Sample

DSA C#

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

This code searches for a target number in a sorted array using binary search and returns its index or -1 if not found.

Execution Table

Step	Operation	low	high	mid	Comparison	Action	Array State
1	Initialize	0	6	-	-	-	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	arr[3]=7 vs target=9	7 < 9 → low=mid+1=4	[1, 3, 5, 7, 9, 11, 13]
3	Calculate mid	4	6	5	arr[5]=11 vs target=9	11 > 9 → high=mid-1=4	[1, 3, 5, 7, 9, 11, 13]
4	Calculate mid	4	4	4	arr[4]=9 vs target=9	Found target at index 4	[1, 3, 5, 7, 9, 11, 13]
5	Exit	4	4	4	-	Return 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	Final
low	0	4	4	4	4
high	6	6	4	4	4
mid	-	3	5	4	4

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 logic fails. See execution_table rows 2 and 3 where we adjust low and high based on comparisons.

Why do we update low to mid + 1 when arr[mid] < target?

Because if the middle element is less than the target, the target can only be in the right half beyond mid. So we move low to mid + 1 to ignore the left half. Refer to execution_table row 2.

What stops the search loop?

The loop stops when low becomes greater than high, meaning the target is not in the array, or when the target is found at mid. See execution_table row 5 where the target is found and the search ends.

Visual Quiz - 3 Questions

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

A 3

B 5

C 4

D 6

💡 Hint

Check the 'mid' column in execution_table row 3.

At which step does the condition low <= high become false if the target is not found?

A Step 4

B Step 5

C After the last iteration when low > high

D Step 2

💡 Hint

Look at the exit_note and understand when the loop stops if target is missing.

If the target was 12 instead of 9, how would the 'low' variable change after step 2?

A low would become 4

B low would become 6

C low would remain 0

D low would become 5

💡 Hint

Compare the comparison and action in execution_table row 2 and imagine target=12.

Concept Snapshot

Binary Search requires a sorted array.
Start with low=0 and high=length-1.
Find mid = (low + high) / 2.
Compare target with arr[mid].
If equal, return mid.
If target > arr[mid], search right half (low=mid+1).
Else search left half (high=mid-1).
Repeat until low > high or found.

Full Transcript

Binary search works only on sorted arrays. It starts by setting low and high pointers to the start and end of the array. Then it calculates the middle index and compares the target value with the middle element. If they match, it returns the index. If the target is greater, it moves the low pointer to mid + 1 to search the right half. If smaller, it moves the high pointer to mid - 1 to search the left half. This process repeats until the target is found or the search space is empty (low > high). This method is efficient because it halves the search space each time, unlike linear search which checks every element.

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