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.

Answer 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).