Why Binary Search and What Sorted Order Gives You in DSA Javascript - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search on Sorted Array

What is the output of the following JavaScript code that performs binary search on a sorted array to find the index of number 7?

DSA Javascript

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

const sortedArray = [1, 3, 5, 7, 9, 11];
console.log(binarySearch(sortedArray, 7));

A -1

B 3

C 2

D 4

💡 Hint

Remember that array indices start at 0 and the array is sorted.

The number 7 is at index 3 in the sorted array [1, 3, 5, 7, 9, 11]. Binary search finds it by checking the middle element and narrowing the search range.

🧠 Conceptual

intermediate

Why Must the Array Be Sorted for Binary Search?

Why is it necessary for the array to be sorted before performing binary search?

A Because binary search requires the array to be reversed first.

B Because binary search only works on arrays with unique elements.

C Because binary search compares the target with the middle element to decide which half to search next, which only works if the array is sorted.

D Because binary search can only find the first element in any array.

💡 Hint

Think about how binary search decides which half of the array to ignore.

Binary search relies on the order of elements to decide whether to search the left or right half. Without sorting, this decision cannot be made correctly.

❓ Predict Output

advanced

Binary Search Result on Unsorted Array

What is the output of this JavaScript code that runs binary search on an unsorted array to find number 7?

DSA Javascript

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

const unsortedArray = [9, 1, 11, 3, 7, 5];
console.log(binarySearch(unsortedArray, 7));

A -1

B 3

C 2

D 0

💡 Hint

Binary search assumes sorted order; what happens if the array is not sorted?

Binary search on an unsorted array does not guarantee correct results. It may fail to find the target even if it exists.

🧠 Conceptual

advanced

Effect of Sorted Order on Search Efficiency

How does having a sorted array improve the efficiency of searching compared to an unsorted array?

A Sorted arrays allow binary search, which reduces the search steps from linear to logarithmic time.

B Sorted arrays allow linear search to run faster than on unsorted arrays.

C Sorted arrays require more steps to search because elements are arranged in order.

D Sorted arrays do not affect search efficiency; search time is always the same.

💡 Hint

Think about how many elements you can ignore each step in binary search.

Binary search on sorted arrays cuts the search space in half each step, making it much faster than checking each element one by one.

🚀 Application

expert

Final Position After Multiple Binary Search Steps

Given the sorted array [2, 4, 6, 8, 10, 12, 14] and target 10, after two iterations of the binary search loop, what is the value of the variable 'left'?

DSA Javascript

const arr = [2, 4, 6, 8, 10, 12, 14];
const target = 10;
let left = 0;
let right = arr.length - 1;

// First iteration
let mid = Math.floor((left + right) / 2);
if (arr[mid] < target) {
  left = mid + 1;
} else {
  right = mid - 1;
}

// Second iteration
mid = Math.floor((left + right) / 2);
if (arr[mid] < target) {
  left = mid + 1;
} else {
  right = mid - 1;
}

console.log(left);

A 3

B 5

C 2

D 4

💡 Hint

Trace the values of left, right, and mid after each iteration carefully.

After the first iteration, left becomes 4 (mid=3, arr[3]=8 < 10). After the second iteration, mid=5, arr[5]=12 > 10, right=4, left remains 4.

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