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.

Practice

1. Why is binary search only applicable on a sorted list?

easy

A. Because it can search any list regardless of order

B. Because it relies on comparing the middle element to decide which half to search next

C. Because it checks every element one by one

D. Because it sorts the list before searching

Solution

1. Step 1: Understand binary search logic

   Binary search works by comparing the middle element to the target and deciding which half to continue searching.

2. Step 2: Importance of sorted order

   This logic only works if the list is sorted, so we know which half contains the target based on comparison.

3. Final Answer:

   Because it relies on comparing the middle element to decide which half to search next -> Option B

4. Quick Check:

   Binary search needs sorted list = Because it relies on comparing the middle element to decide which half to search next [OK]

Hint: Binary search splits sorted list by middle comparison [OK]

Common Mistakes:

• Thinking binary search works on unsorted lists
• Confusing binary search with linear search
• Assuming binary search sorts the list automatically

2. Which of the following is the correct syntax to find the middle index in a binary search on array arr between indices low and high in JavaScript?

easy

A. const mid = Math.floor((low + high) / 2);

B. const mid = (low + high) / 2;

C. const mid = Math.ceil((low + high) / 2);

D. const mid = low + high;

Solution

1. Step 1: Calculate middle index correctly

   The middle index should be the floor of the average of low and high to get an integer index.

2. Step 2: Check each option

   const mid = Math.floor((low + high) / 2); uses Math.floor which correctly rounds down. const mid = (low + high) / 2; returns a float, const mid = Math.ceil((low + high) / 2); rounds up which can cause errors, const mid = low + high; sums indices without division.

3. Final Answer:

   const mid = Math.floor((low + high) / 2); -> Option A

4. Quick Check:

   Use Math.floor for middle index [OK]

Hint: Use Math.floor to get integer middle index [OK]

Common Mistakes:

• Not using Math.floor causing float index
• Using Math.ceil causing off-by-one errors
• Adding indices without dividing

3. What will be the output of the following JavaScript code?

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

medium

A. 3

B. 2

C. -1

D. 4

Solution

1. Step 1: Trace binary search steps for target 8

   Initial low=0, high=4, mid=2 (value 6). Since 6 < 8, low = mid+1 = 3.

2. Step 2: Next iteration mid=3 (value 8), matches target, return 3

   The function returns index 3 where 8 is found.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Index of 8 in array = 3 [OK]

Hint: Trace mid updates to find target index [OK]

Common Mistakes:

• Confusing index with value
• Off-by-one errors in mid calculation
• Returning -1 incorrectly

4. The following binary search code has a bug. What is the error?

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

medium

A. The loop condition should be low < high, not low <= high

B. low should start at 1, not 0

C. mid calculation should use Math.ceil instead of Math.floor

D. high should be initialized to arr.length - 1, not arr.length

Solution

1. Step 1: Check initialization of high

   Array indices go from 0 to length-1, so high must be arr.length - 1 to avoid out-of-bounds.

2. Step 2: Consequences of wrong high value

   Setting high = arr.length causes mid to sometimes be arr.length, which is invalid index and causes errors.

3. Final Answer:

   high should be initialized to arr.length - 1, not arr.length -> Option D

4. Quick Check:

   High index = length - 1 [OK]

Hint: High index must be last valid array index [OK]

Common Mistakes:

• Setting high to arr.length causing index errors
• Changing low start incorrectly
• Changing loop condition wrongly

5. You have a sorted array arr = [1, 3, 3, 5, 7, 7, 7, 9]. You want to find the first occurrence of the number 7 using binary search. Which modification helps achieve this?

hard

A. Use linear search instead of binary search

B. Return mid immediately when arr[mid] equals target

C. When arr[mid] equals target, continue searching left half to find first occurrence

D. Search right half when arr[mid] equals target

Solution

1. Step 1: Understand duplicate elements in sorted array

   Binary search normally returns any matching index, but to find first occurrence, we must check if earlier indices also have the target.

2. Step 2: Modify search to continue left when target found

   When arr[mid] equals target, update result but continue searching left half to find earlier occurrence.

3. Final Answer:

   When arr[mid] equals target, continue searching left half to find first occurrence -> Option C

4. Quick Check:

   Search left half on match for first occurrence [OK]

Hint: On match, search left half to find first occurrence [OK]

Common Mistakes:

• Returning immediately on first match
• Searching right half on match
• Using linear search unnecessarily