// solution 1 : via iteration
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let high = nums.length - 1;
  let low = 0;

  while (low <= high) {
    let mid = parseInt((low + high) / 2);

    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] > target) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  return -1;
};

// Solution 2 : via recursion
const searchRecursive = function (nums, target) {
  let n = nums.length;
  const binarySearch = function (nums, low, high, target) {
    if (high >= low) {
      let mid = parseInt((low + high) / 2);

      // If the element is present at the middle
      // itself
      if (nums[mid] == target) return mid;

      // If element is smaller than mid, then
      // it can only be present in left subarray
      if (nums[mid] > target) return binarySearch(nums, low, mid - 1, target);

      // Else the element can only be present
      // in right subarray
      return binarySearch(nums, mid + 1, high, target);
    }

    // We reach here when element is not
    // present in array
    return -1;
  };

  return binarySearch(nums, 0, n - 1, target);
};

searchRecursive([-1, 0, 3, 5, 9, 12], 9);