JavaScript: Binary Search Algorithm using recursion

JavaScript Function: Exercise-12 with Solution

Recursive Binary Search in Array

Write a JavaScript program to search for a given integer in an array of sorted integers using the Binary Search Algorithm and recursion.

Test Data:
([1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 17, 19, 20, 22, 23], 6) -> 4
([1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 17, 19, 20, 22, 23], 16) -> -1

Sample Solution-1:

JavaScript Code:

// Recursive binary search function
const binarySearch = (arr, target, start = 0, end = arr.length - 1) => {
  // Base case: target not found
  if (start > end) {
    return -1;
  }
  // Calculate middle index
  const mid = Math.floor((start + end) / 2);
  // Check if target is at the middle
  if (arr[mid] === target) {
    return mid;
  }
  // If target is smaller, search in the left half
  if (arr[mid] > target) {
    return binarySearch(arr, target, start, mid - 1);
  }
  // If target is larger, search in the right half
  return binarySearch(arr, target, mid + 1, end);
};
// Test the binary search function
const sortedArray1 = [1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 17, 19, 20, 22, 23]
const target1 = 6;
const sortedArray2 = [1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 17, 19, 20, 22, 23]
const target2 = -1;
console.log(`Index of ${target1}: ${binarySearch(sortedArray1, target1)}`);
console.log(`Index of ${target2}: ${binarySearch(sortedArray2, target2)}`); 

Output:

Index of 6: 4
Index of -1: -1

Flowchart:

Live Demo:

See the Pen javascript-recursion-function-exercise-12 by w3resource (@w3resource) on CodePen.

Sample Solution-2:

JavaScript Code:

// Iterative binary search function
const binarySearchIterative = (arr, target) => {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    const mid = Math.floor((start + end) / 2);

    if (arr[mid] === target) {
      return mid; // Target found
    }

    if (arr[mid] < target) {
      start = mid + 1; // Search in the right half
    } else {
      end = mid - 1; // Search in the left half
    }
  }

  return -1; // Target not found
};
// Test the binary search function
const sortedArray1 = [1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 17, 19, 20, 22, 23]
const target1 = 6;
const sortedArray2 = [1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 17, 19, 20, 22, 23]
const target2 = -1;
console.log(`Index of ${target1}: ${binarySearchIterative(sortedArray1, target1)}`);
console.log(`Index of ${target2}: ${binarySearchIterative(sortedArray2, target2)}`); 

Output:

Index of 6: 4
Index of -1: -1

Flowchart:

For more Practice: Solve these Related Problems:

• Write a JavaScript function that implements recursive binary search on a sorted array and returns the target's index.
• Write a JavaScript function that recursively searches for a target in an array and returns -1 if it is not found.
• Write a JavaScript function that uses recursion for binary search and properly handles arrays with duplicate elements.
• Write a JavaScript function that validates the array input and recursively performs binary search, returning the index or -1.

Improve this sample solution and post your code through Disqus.

Previous: Convert Binary to Decimal using recursion.
Next:Letter combinations of a number.