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 and high pointers

↓

Calculate mid = (low + high) / 2

↓

Compare target with array[mid

↓

Move high

↓

Repeat until low > high

↓

Target not found

Binary search works on sorted arrays by repeatedly dividing the search range in half, comparing the middle element to the target, and narrowing the search until the target is found or the range is empty.

Execution Sample

DSA C++

int binarySearch(int arr[], int size, int target) {
  int low = 0, high = size - 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;
}

This code searches for a target value in a sorted array by repeatedly checking the middle element and adjusting the search range.

Execution Table

Step	Operation	low	high	mid	Comparison	Action	Search Range Visual
1	Initialize low and high	0	6	-	-	Start search	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	arr[3]=7 vs target=9	target > mid, move low	[1, 3, 5, 7, 9, 11, 13]
3	Update low	4	6	-	-	-	[9, 11, 13]
4	Calculate mid	4	6	5	arr[5]=11 vs target=9	target < mid, move high	[9, 11, 13]
5	Update high	4	4	-	-	-	[9]
6	Calculate mid	4	4	4	arr[4]=9 vs target=9	target == mid, found	[9]
7	Return index	-	-	-	-	Return 4	[9]

💡 Search ends when target is found at index 4 or when low > high if target not found.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
low	0	0	4	4	4	4	-
high	6	6	6	6	4	4	-
mid	-	3	-	5	-	4	-
target	9	9	9	9	9	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 logic fails. See execution_table steps 2 and 4 where the search range is narrowed based on comparisons.

Why do we update 'low' to mid + 1 and 'high' to mid - 1 instead of just mid?

Because mid has already been checked and does not match the target, so we exclude it from the next search range. This avoids infinite loops. Refer to execution_table steps 3 and 5 where low and high are adjusted accordingly.

What happens if the target is not in the array?

The search range will eventually become invalid (low > high), causing the loop to stop and return -1. This is shown in the exit_note and the loop condition in the code.

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' column in execution_table row for step 4.

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

A Step 3

B Step 6

C Step 5

D Step 2

💡 Hint

Look at the 'Search Range Visual' column to see when only one element remains.

If the target was 12 instead of 9, what would happen at step 6?

A Search ends with target not found

B Search continues with low updated

C Target found at index 4

D High pointer moves to mid - 1

💡 Hint

Consider the exit condition when target is not found and low > high.

Concept Snapshot

Binary Search requires a sorted array.
Start with low=0 and high=size-1.
Find mid = (low + high) / 2.
Compare target with arr[mid].
If equal, return mid.
If target > arr[mid], move low to mid+1.
If target < arr[mid], move high to mid-1.
Repeat until low > high (target not found).

Full Transcript

Binary search is a fast way to find a target in a sorted array. It works by repeatedly dividing the search range in half. We start with two pointers: low at the start and high at the end of the array. We find the middle index mid and compare the target with the element at mid. If they match, we return mid. If the target is greater, we move low to mid + 1 to search the right half. If the target is smaller, we move high to mid - 1 to search the left half. We repeat this until low is greater than high, which means the target is not in the array. This method is much faster than checking each element one by one, but it only works if the array is sorted.