The debate: Using Recursion versus Not Using Recursion in a JavaScript Binary Search Algorithm for Arrays

Question

The debate: Using Recursion versus Not Using Recursion in a JavaScript Binary Search Algorithm for Arrays

I have come up with a recursive method to identify a unique item in an array (where all other items appear in pairs next to each other). I am wondering if it's possible to achieve the same result without recursion, perhaps using a while loop. Additionally, I am curious whether utilizing a loop within the function consumes less memory compared to recursion?

Solution at present:

function findSingularElement(arr, low, high) {
  // base cases
  if (arr.length < 3) return console.log('Invalid length of array.');
  if (low > high) return;
  if (low == high) return console.log(arr[low]);

  var mid = low + (high - low) / 2;

  if (mid % 2 === 0) {
    if (arr[mid] == arr[mid + 1]) {
      return findSingularElement(arr, mid + 2, high);
    } else {
      return findSingularElement(arr, low, mid);
    }
  } else {
    if (arr[mid] == arr[mid - 1]) {
      return findSingularElement(arr, mid + 1, high);
    } else {
      return findSingularElement(arr, low, mid - 1);
    }
  }
}

var array = [1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 8];

Appreciate any insights.

javascript arrays recursion binary-search

Answer 1

Answer №1

To eliminate recursion from your function, simply swap out recursive calls with appropriate variable assignments:

function findSingularElement1(arr) {
    if (arr.length < 3)
        throw('Invalid length of array.');

    var low = 0, high = arr.length - 1;

    while (low < high) {

        var mid = low + (high - low) / 2;

        if (mid % 2 === 0) {
            if (arr[mid] == arr[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        } else {
            if (arr[mid] == arr[mid - 1]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return low == high ? arr[low] : null;
}

However, it appears that the entire approach you are taking is overly complex. You can easily identify an unpaired item using a simple loop:

for (var i = 0; i < array.length; i += 2)
    if (array[i] != array[i + 1])
        return array[i];

(Assuming the array is sorted, and each item occurs exactly once or twice).

Answer 2

To eliminate recursion from your function, simply swap out recursive calls with appropriate variable assignments:

function findSingularElement1(arr) {
    if (arr.length < 3)
        throw('Invalid length of array.');

    var low = 0, high = arr.length - 1;

    while (low < high) {

        var mid = low + (high - low) / 2;

        if (mid % 2 === 0) {
            if (arr[mid] == arr[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        } else {
            if (arr[mid] == arr[mid - 1]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return low == high ? arr[low] : null;
}

However, it appears that the entire approach you are taking is overly complex. You can easily identify an unpaired item using a simple loop:

for (var i = 0; i < array.length; i += 2)
    if (array[i] != array[i + 1])
        return array[i];

(Assuming the array is sorted, and each item occurs exactly once or twice).

Answer 3

Answer №2

Just for fun, here's my playful response!

let numArray = [2, 4, 7, 13, 15, 18, 22, 31, 39, 42, 57, 79];

function recursiveSearch(sortedArr, key, startIdx, endIdx) {
    let startIdx = startIdx || 0;
    let endIdx = endIdx || sortedArr.length;
    let midIdx = Math.floor((startIdx + endIdx) / 2);

    if (startIdx > endIdx) {
        return -1;
    }

    if (key === sortedArr[midIdx]) {
        return sortedArr[midIdx];
    } else if (key < sortedArr[midIdx]) {
        return recursiveSearch(sortedArr, key, startIdx, midIdx - 1);
    } else if (key > sortedArr[midIdx]) {
        return recursiveSearch(sortedArr, key, midIdx + 1, endIdx);
    }
}

let total = recursiveSearch(numArray, 15);

Answer 4

Just for fun, here's my playful response!

let numArray = [2, 4, 7, 13, 15, 18, 22, 31, 39, 42, 57, 79];

function recursiveSearch(sortedArr, key, startIdx, endIdx) {
    let startIdx = startIdx || 0;
    let endIdx = endIdx || sortedArr.length;
    let midIdx = Math.floor((startIdx + endIdx) / 2);

    if (startIdx > endIdx) {
        return -1;
    }

    if (key === sortedArr[midIdx]) {
        return sortedArr[midIdx];
    } else if (key < sortedArr[midIdx]) {
        return recursiveSearch(sortedArr, key, startIdx, midIdx - 1);
    } else if (key > sortedArr[midIdx]) {
        return recursiveSearch(sortedArr, key, midIdx + 1, endIdx);
    }
}

let total = recursiveSearch(numArray, 15);

Answer 5

Answer №3

When it comes to using recursion in programming, there is always the option to replace it with loops. Recursion does have its benefits though, as it can make the code more straightforward and organized. In a binary search scenario, recursion can be swapped out for a loop by updating the base condition accordingly.

 function binarySearch(arr,ele){
  let low = 0;
  let high = arr.length-1;
  while(low<=high){
   let mid = Math.floor((low+high)/2) 
   if(arr[mid]==ele) 
     return true;
   else if(arr[mid]>ele)
     high = mid-1;
   else
     low = mid+1;
    }
  return false;
 }

Answer 6

When it comes to using recursion in programming, there is always the option to replace it with loops. Recursion does have its benefits though, as it can make the code more straightforward and organized. In a binary search scenario, recursion can be swapped out for a loop by updating the base condition accordingly.

 function binarySearch(arr,ele){
  let low = 0;
  let high = arr.length-1;
  while(low<=high){
   let mid = Math.floor((low+high)/2) 
   if(arr[mid]==ele) 
     return true;
   else if(arr[mid]>ele)
     high = mid-1;
   else
     low = mid+1;
    }
  return false;
 }

The debate: Using Recursion versus Not Using Recursion in a JavaScript Binary Search Algorithm for Arrays

Answer №1

Answer №2

Answer №3

Similar questions

The process in mocha does not execute when using await

PHP - Determine the number of elements in an array by comparing it to another

Showcasing interactive column titles by employing angularjs in an html table

Indicating that jQuery is not recognized despite the jQuery file being successfully loaded

Creating a smooth transition effect for a welcoming message using PHP upon logging in

The Distinction Between "Q" and "q" in AngularJS and RequireJS

The essence of the argument becomes muddled when implementing bind apply with arrays as arguments

Inspect Element: JSON data is being displayed rather than the expected HTML source code

Exploring querying techniques in Node.js

Updates cannot be flushed while React is currently rendering

AngularJS: Implement ng-repeat directive to generate two separate HTML containers

Changing image using setInterval() with class in p5.js

Finding the index of a nested div element with a click event using jQuery

Steps for creating checkboxes for individual table rows in HTML using embedded PHP and updating their values in a PostgreSQL database:1. Begin by iterating through each

Choose rows from a NumPy array in a random manner depending on a specific condition

Step-by-step guide to automatically check a checkbox when a field is updated

Transmit information from JavaScript to a servlet and receive a response in return

Sort the observable data by a value returned from an API request

Limit the number input to only allow values between 0 and 100

Setting up the Angular 2 router to function from the /src subfolder