Binary Search Recursive Approach in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the binary search algorithm?

Binary search finds an item in a sorted list by repeatedly dividing the search interval in half, checking the middle element, and deciding which half to search next.

beginner

In the recursive binary search, what are the base cases?

The base cases are when the search interval is empty (start index > end index), meaning the item is not found, or when the middle element equals the target, meaning the item is found.

beginner

Why must the input array be sorted for binary search to work?

Because binary search decides which half to search based on comparisons, the array must be sorted to guarantee that all smaller elements are on one side and larger on the other.

intermediate

What parameters are typically passed in a recursive binary search function?

The function usually takes the array, the target value, the start index, and the end index to define the current search interval.

intermediate

How does the recursive binary search reduce the problem size at each step?

It calculates the middle index and then calls itself on either the left half or the right half of the array, effectively halving the search space each time.

What is the time complexity of binary search in the worst case?

A O(n log n)

B O(n)

C O(log n)

D O(1)

Binary search divides the search space in half each time, leading to a logarithmic time complexity O(log n).

In recursive binary search, what happens if the target is less than the middle element?

A Search the left half

B Search the right half

C Return -1 immediately

D Return the middle index

If the target is less than the middle element, the search continues recursively on the left half.

Which of these is NOT a parameter in a typical recursive binary search function?

A Start and end indices of the search range

B Target value

C Array to search

D Current index of the target

The current index of the target is not known beforehand; the function uses start and end indices to narrow the search.

What should the recursive binary search function return if the target is not found?

A The middle index

B -1 or a sentinel value

C 0

D The start index

Returning -1 or a sentinel value indicates the target is not present in the array.

Why is recursion useful in binary search?

A It makes the code shorter and easier to understand by breaking the problem into smaller parts.

B It makes the search faster than iterative methods.

C It avoids the need for a sorted array.

D It uses more memory but less CPU.

Recursion simplifies the code by handling smaller subproblems, though iterative binary search can be equally efficient.

Explain how recursive binary search works step-by-step on a sorted array.

Think about how the problem size reduces each time.

Describe the base cases in recursive binary search and why they are important.

Base cases stop the recursion and give the answer.

Practice

1. What is the main idea behind the binary search recursive approach when searching for a value in a sorted array?

easy

A. Divide the array into halves and search recursively in the half where the value can be.

B. Check every element one by one from start to end.

C. Sort the array first and then search linearly.

D. Use a loop to check elements until the value is found.

Solution

1. Step 1: Understand binary search logic

   Binary search works by dividing the sorted array into two halves and deciding which half to search next based on comparison.

2. Step 2: Recognize recursive approach

   In recursion, the function calls itself on the half where the target value may exist, reducing the search space each time.

3. Final Answer:

   Divide the array into halves and search recursively in the half where the value can be. -> Option A

4. Quick Check:

   Binary search = divide and conquer [OK]

Hint: Remember: binary search splits array, recursion repeats on half [OK]

Common Mistakes:

• Thinking binary search checks every element linearly
• Confusing recursion with iteration
• Not requiring the array to be sorted

2. Which of the following is the correct base case condition in a recursive binary search function in JavaScript?

easy

A. if (array.length == 0) return 0;

B. if (start > end) return -1;

C. if (start == end) return start;

D. if (mid == target) return mid + 1;

Solution

1. Step 1: Identify base case meaning

   The base case stops recursion when the search space is empty, which happens if start index passes end index.

2. Step 2: Match base case condition

   The condition start > end means no elements left to search, so return -1 to indicate not found.

3. Final Answer:

   if (start > end) return -1; -> Option B

4. Quick Check:

   Base case = empty search space [OK]

Hint: Base case ends recursion when start passes end [OK]

Common Mistakes:

• Using incorrect comparison like start == end as base case
• Returning wrong index or value in base case
• Confusing base case with recursive step

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

function binarySearch(arr, target, start, end) {
  if (start > end) return -1;
  const mid = Math.floor((start + end) / 2);
  if (arr[mid] === target) return mid;
  else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
  else return binarySearch(arr, target, mid + 1, end);
}

const array = [2, 4, 6, 8, 10];
console.log(binarySearch(array, 6, 0, array.length - 1));

medium

A. 2

B. 3

C. -1

D. 1

Solution

1. Step 1: Trace initial call

   Start=0, end=4, mid=2 (element 6). Since arr[mid] == target (6), return mid = 2.

2. Step 2: Confirm output

   The function returns 2 immediately without further recursion.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target found at index 2 [OK]

Hint: Check mid index value first to find target quickly [OK]

Common Mistakes:

• Miscomputing mid index
• Confusing index with value
• Forgetting zero-based indexing

4. Identify the error in the following recursive binary search function and choose the correct fix.

function binarySearch(arr, target, start, end) {
  if (start >= end) return -1;
  const mid = Math.floor((start + end) / 2);
  if (arr[mid] === target) return mid;
  else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
  else return binarySearch(arr, target, mid + 1, end);
}

medium

A. Change mid calculation to (start + end + 1) / 2;

B. Remove else if and use only if statements.

C. Return mid + 1 when found instead of mid;

D. Change base case to if (start > end) return -1;

Solution

1. Step 1: Analyze base case condition

   The base case incorrectly uses start >= end, which misses the case when start == end and the element could still be at that index.

2. Step 2: Correct base case

   Changing it to start > end ensures the search includes the last element before stopping.

3. Final Answer:

   Change base case to if (start > end) return -1; -> Option D

4. Quick Check:

   Base case must allow start == end check [OK]

Hint: Base case should allow checking when start equals end [OK]

Common Mistakes:

• Stopping search too early by wrong base case
• Changing mid calculation unnecessarily
• Returning wrong index on success

5. Given a sorted array with possible duplicate values, how can you modify the recursive binary search to find the first occurrence of a target value?

hard

A. Search right half only when arr[mid] == target.

B. Return mid immediately when arr[mid] == target without further search.

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

D. Use linear search after binary search to find first occurrence.

Solution

1. Step 1: Understand duplicates in binary search

   Standard binary search returns any occurrence, but to find first occurrence, we must check if earlier duplicates exist.

2. Step 2: Modify recursion on match

   When arr[mid] == target, recursively search left half to find if an earlier occurrence exists; if none, mid is first occurrence.

3. Final Answer:

   When arr[mid] == target, continue searching left half to find earlier occurrence. -> Option C

4. Quick Check:

   Find first occurrence by searching left on match [OK]

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

Common Mistakes:

• Returning first found index without checking left side
• Searching right half on match incorrectly
• Using linear search unnecessarily