Recursion vs No Recursion in JS Binary Search on Array

Question

I've written out a recursive method for finding a single item in an array which is not repeated (whereas all other items are in pairs and next to one another). My question is, can this be done without recursion (perhaps with a while loop) and is using a loop within the function more effective (in terms of memory) than just using recursion?

Current solution:

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];

Thank you.

"yes" to both questions... )) Instead of rec calls, just update low and high and loop while low <= high. — georg
– georg, Commented Sep 19, 2016 at 23:08
If you think about how recursion actually works, with pushing stuff onto the stack and whatnot, any recursive algorithm can be rewritten using loops. — qxz
– qxz, Commented Sep 19, 2016 at 23:37
@georg I'm going in circles here (no pun intended). Would you mind responding with an example? I'm beginning to go cross-eyed. — Jose
– Jose, Commented Sep 20, 2016 at 3:48

georg · Accepted Answer · 2016-09-20 09:09:45Z

1

To remove recursion from your function, just replace 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;
}

That said, your whole approach seems overcomplicated, you can easily find an unpaired item with 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).

answered Sep 20, 2016 at 9:09

georg

216k57 gold badges324 silver badges401 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Jose Over a year ago

Thank you. You're correct that binary search seems like overkill for this. I think the intention behind this was to just practice more binary search, thanks again!

jorblume · Accepted Answer · 2017-02-28 04:38:54Z

1

My answer, just having fun!

var numberArray = [1, 3, 6, 8, 9, 11, 16, 27, 33, 37, 56, 78];

function recursiveBinary(sortedArray, target, start, end) {
    var start = start || 0;
  var end = end || sortedArray.length;
    var middle = Math.floor((start + end) / 2);

    if (start > end) {
    return -1;
  }

  if (target === sortedArray[middle]) {
    return sortedArray[middle];
  } else if (target < sortedArray[middle]) {
    return recursiveBinary(sortedArray, target, start, middle - 1);
  } else if (target > sortedArray[middle]) {
    return recursiveBinary(sortedArray, target, middle + 1, end);
  }

}

var sum = recursiveBinary(numberArray, 9);

answered Feb 28, 2017 at 4:38

jorblume

6077 silver badges20 bronze badges

Comments

Arpit Bajpai · Accepted Answer · 2020-07-17 15:12:12Z

0

Anything that is done with recursion, can be replaced by loops. The only thing that recursion can do and loops can't is making the code easy and clean. Recursion can be removed in a binary search by replacing the base condition with a loop.

 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;
 }

edited Jul 17, 2020 at 15:12

answered Jul 15, 2020 at 21:31

Arpit Bajpai

1981 gold badge6 silver badges17 bronze badges

Collectives™ on Stack Overflow

Recursion vs No Recursion in JS Binary Search on Array

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related