Binary Search vs Linear Search Real Cost Difference in DSA Javascript - Key Differences

Recall & Review

beginner

What is the main difference between linear search and binary search?

Linear search checks each item one by one until it finds the target or reaches the end. Binary search splits the list in half repeatedly to find the target faster but requires the list to be sorted.

beginner

Why does binary search require a sorted list?

Binary search depends on comparing the middle item to the target to decide which half to search next. If the list is not sorted, this logic breaks and the search won't work correctly.

intermediate

What is the time complexity of linear search and binary search?

Linear search has a time complexity of O(n), meaning it may check every item. Binary search has a time complexity of O(log n), meaning it cuts the search space in half each step, making it much faster on large lists.

intermediate

In what situation might linear search be better than binary search?

If the list is small or unsorted, linear search can be simpler and faster because binary search requires sorting first, which takes extra time.

beginner

Explain the real cost difference between binary search and linear search in simple terms.

Linear search looks at each item one by one, so it can be slow if the list is big. Binary search quickly jumps to the middle and cuts the list in half each time, so it finds things much faster but only if the list is sorted.

Which search method requires the list to be sorted?

A Binary Search

B Linear Search

C Both

D Neither

Binary search only works correctly if the list is sorted because it decides which half to search based on comparisons.

What is the worst-case time complexity of linear search?

A O(n)

B O(1)

C O(n log n)

D O(log n)

Linear search may need to check every item, so its worst-case time is O(n).

How does binary search reduce the search space each step?

A By removing all items except one

B By removing one item

C By removing a quarter of the items

D By removing half the items

Binary search cuts the list in half each time, quickly narrowing down where the target can be.

When might linear search be preferred over binary search?

A When the list is very large and sorted

B When the list is sorted and large

C When the list is small or unsorted

D Never

Linear search is simple and works on unsorted lists, so it can be better for small or unsorted data.

Which search is generally faster on large sorted lists?

A Linear Search

B Binary Search

C Both are the same

D Depends on the data

Binary search is much faster on large sorted lists because it reduces the search space quickly.

Describe how binary search works and why it is faster than linear search on sorted lists.

Think about cutting the search area in half each time.

Explain when you would choose linear search over binary search and why.

Consider the cost of sorting and list size.

Practice

1. Which search method is generally faster for finding an element in a sorted list of 1,000,000 items?

easy

A. Binary Search

B. Linear Search

C. Both are equally fast

D. Neither works on sorted lists

Solution

1. Step 1: Understand search methods on sorted lists

   Binary Search divides the list repeatedly, reducing search space quickly. Linear Search checks each item one by one.

2. Step 2: Compare efficiency on large sorted lists

   Binary Search runs in about log2(1,000,000) ≈ 20 steps, Linear Search may take up to 1,000,000 steps.

3. Final Answer:

   Binary Search -> Option A

4. Quick Check:

   Binary Search is faster on sorted lists [OK]

Hint: Binary Search halves search space; Linear checks all [OK]

Common Mistakes:

• Thinking Linear Search is faster on sorted lists
• Confusing sorted and unsorted list efficiency
• Ignoring logarithmic speed of Binary Search

2. Which of the following is the correct syntax to start a binary search on a sorted array arr in JavaScript?

easy

A. let mid = (start + end) / 2;

B. let mid = start - end;

C. let mid = start + end;

D. let mid = Math.floor((start + end) / 2);

Solution

1. Step 1: Calculate middle index correctly

   Binary Search finds middle by averaging start and end indices, then flooring to get integer index.

2. Step 2: Check each option for correctness

   let mid = Math.floor((start + end) / 2); uses Math.floor to get integer mid index; others either don't floor or use wrong operations.

3. Final Answer:

   let mid = Math.floor((start + end) / 2); -> Option D

4. Quick Check:

   Floor average of start and end gives mid [OK]

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

Common Mistakes:

• Not using Math.floor causing float index
• Adding or subtracting indices incorrectly
• Using mid as sum without division

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

const arr = [2, 4, 6, 8, 10];
function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) return i;
  }
  return -1;
}
console.log(linearSearch(arr, 8));

medium

A. -1

B. 2

C. 3

D. 4

Solution

1. Step 1: Trace the linear search loop

   The function checks each element: arr[0]=2, arr[1]=4, arr[2]=6, arr[3]=8 matches target 8.

2. Step 2: Return index when target found

   At index 3, target 8 is found, so function returns 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Index of 8 in array is 3 [OK]

Hint: Linear search returns index of first match [OK]

Common Mistakes:

• Returning value instead of index
• Off-by-one errors in loop
• Confusing index with element value

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

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

medium

A. end should be initialized to arr.length - 1

B. start should be initialized to 1

C. mid calculation is incorrect

D. Loop condition should be start < end

Solution

1. Step 1: Check initialization of end index

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

2. Step 2: Understand loop condition and mid usage

   With end = arr.length, mid can be arr.length which is invalid index, causing error.

3. Final Answer:

   end should be initialized to arr.length - 1 -> Option A

4. Quick Check:

   Array last index = length - 1 [OK]

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

Common Mistakes:

• Setting end to arr.length causing index error
• Changing start incorrectly
• Using wrong loop condition

5. You have a sorted array of 1,000,000 numbers and want to find if the number 500,000 exists. Which search method will minimize the average number of comparisons, and why?

hard

A. Linear Search, because it checks elements sequentially

B. Binary Search, because it reduces search space by half each step

C. Linear Search, because it is simpler to implement

D. Binary Search, but only if the array is unsorted

Solution

1. Step 1: Analyze search methods on large sorted arrays

   Linear Search checks elements one by one, averaging 500,000 comparisons for half the array.

2. Step 2: Understand Binary Search efficiency

   Binary Search halves the search space each step, needing about log2(1,000,000) ≈ 20 comparisons.

3. Step 3: Compare average comparisons

   20 comparisons (Binary Search) is much less than 500,000 (Linear Search), so Binary Search is better.

4. Final Answer:

   Binary Search, because it reduces search space by half each step -> Option B

5. Quick Check:

   Binary Search uses log steps, fewer comparisons [OK]

Hint: Binary Search halves search space, fewer checks [OK]

Common Mistakes:

• Choosing Linear Search for sorted arrays
• Ignoring logarithmic speed advantage
• Thinking Binary Search needs sorted array but choosing wrong option