Why Binary Search and What Sorted Order Gives You in DSA Javascript - 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 = Math.floor((low + high) / 2)

↓

Compare target with array[mid

↓

Found

↓

End

Binary search works by repeatedly dividing a sorted array in half to find a target value quickly.

Execution Sample

DSA Javascript

const arr = [2, 4, 6, 8, 10];
let low = 0;
let high = arr.length - 1;
let target = 6;
while (low <= high) {
  let mid = Math.floor((low + high) / 2);
  if (arr[mid] === target) {
    console.log('Found target at index', mid);
    break;
  } else if (arr[mid] < target) {
    low = mid + 1;
  } else {
    high = mid - 1;
  }
}

This code searches for the number 6 in a sorted array using binary search.

Execution Table

Step	Operation	low	high	mid	array[mid]	Comparison	Action	Visual State
1	Initialize	0	4	-	-	-	Start search	[2, 4, 6, 8, 10]
2	Calculate mid	0	4	2	6	6 == 6	Found target	[2, 4, 6, 8, 10]
3	End	-	-	-	-	-	Stop search	[2, 4, 6, 8, 10]

💡 Target found at mid index 2, search ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
low	undefined	0	0	0
high	undefined	4	4	4
mid	undefined	-	2	2
target	6	6	6	6

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 to the middle element. If the array is not sorted, this decision is invalid. See execution_table step 2 where mid element comparison guides the search.

What happens if the target is not in the array?

The search keeps adjusting low and high until low > high, meaning the target is not found. The loop ends without finding the target. This is shown by the exit condition in the concept_flow.

Why do we calculate mid as Math.floor((low + high) / 2)?

To find the middle index between low and high, rounding down to avoid fractional index. This ensures we check the middle element correctly, as shown in execution_table step 2.

Visual Quiz - 3 Questions

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

A 3

B 1

C 2

D 0

💡 Hint

Check the 'mid' column in execution_table row for step 2.

At which step does the search find the target?

A Step 1

B Step 2

C Step 3

D Never

💡 Hint

Look at the 'Comparison' and 'Action' columns in execution_table.

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

A It might miss the target or give wrong results

B It would still find the target quickly

C It would run faster

D It would search from the end only

💡 Hint

Refer to key_moments about why sorting is necessary.

Concept Snapshot

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

Full Transcript

Binary search is a fast way to find a number in a sorted list. We start by looking at the middle number. If it matches the number we want, we stop. If the number we want is smaller, we look only at the left half. If it is bigger, we look at the right half. We keep doing this until we find the number or there is no more list to check. This only works if the list is sorted because we rely on the order to decide which half to check next.