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.