JavaScript: Binary search using recursion

JavaScript Function: Exercise-8 with Solution

Binary Search

Write a JavaScript program for binary search.

Sample array : [0,1,2,3,4,5,6]
console.log(l.br_search(5)) will return '5'

Visual Presentation:

Sample Solution-1:

JavaScript Code:

// Extending the prototype of Array to add a binary search method
Array.prototype.br_search = function (target) {
  // Calculate the index of the middle element
  var half = parseInt(this.length / 2);
  
  // Base case: If the target is equal to the middle element, return the index
  if (target === this[half]) {
    return half;
  }
  
  // Recursive case: If the target is greater than the middle element, search the right half
  if (target > this[half]) {
    return half + this.slice(half, this.length).br_search(target);
  } 
  // Recursive case: If the target is less than the middle element, search the left half
  else {
    return this.slice(0, half).br_search(target);
  }
};

// Example usage: Create an array and perform a binary search for the target value
var l = [0, 1, 2, 3, 4, 5, 6];
console.log(l.br_search(5)); // Output: 5 (index of the target value) 

Output:

5

Flowchart:

Live Demo:

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

Sample Solution-2:

JavaScript Code:

// Binary search function using recursion
function binarySearchRecursive(arr, target, start = 0, end = arr.length - 1) {
  // Base case: If the start index is greater than the end index, the target is not found
  if (start > end) {
    return -1;
  }

  // Calculate the index of the middle element
  const mid = Math.floor((start + end) / 2);

  // Base case: If the middle element is equal to the target, return its index
  if (arr[mid] === target) {
    return mid;
  } 
  // Recursive case: If the target is less than the middle element, search the left half
  else if (target < arr[mid]) {
    return binarySearchRecursive(arr, target, start, mid - 1);
  } 
  // Recursive case: If the target is greater than the middle element, search the right half
  else {
    return binarySearchRecursive(arr, target, mid + 1, end);
  }
}

// Example usage: Perform binary search on a sorted array
const sortedArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
const targetValue = 5;
const resultIndex = binarySearchRecursive(sortedArray, targetValue);

// Output the result
if (resultIndex !== -1) {
  console.log(`The target value ${targetValue} is found at index ${resultIndex}.`);
} else {
  console.log(`The target value ${targetValue} is not present in the array.`);
} 

Output:

The target value 5 is found at index 5.

Flowchart:

For more Practice: Solve these Related Problems:

• Write a JavaScript function that implements binary search iteratively on a sorted array.
• Write a JavaScript function that performs recursive binary search and returns the index of the found element.
• Write a JavaScript function that applies binary search on a sorted array of objects based on a specified key.
• Write a JavaScript function that implements binary search and returns the index of the first occurrence when duplicates exist.

Improve this sample solution and post your code through Disqus.

Previous: Write a JavaScript program to check whether a number is even or not.
Next: Write a merge sort program in JavaScript.