"Cracking the coding interview", search, 10.3

cracking-the-coding-interview-10-3.js

/**
 * Находит индекс указанного элемента x в массиве arr.
 * Если такого элемента нет, вернет -1.
 * Работает за O(log n).
 * В худшем случае деградирует до O(n), при большом количестве одинаковых элементов.
 * @param   {array<number>} arr
 * @param   {number} x
 * @returns {number}
 */
const search = (function() {
  return function(arr, x) {
    return search(arr, 0, arr.length - 1, x);
  }
  
  function search(arr, left, right, x) {
    const mid = Math.floor((left + right) / 2);

    if (x === arr[mid]) {
      return mid;
    }
    if (right < left) {
      return -1;
    }

    // рассмотрим три возможных случая:
    // - левая половина упорядочена
    if (arr[left] < arr[mid]) {

      return (arr[left] >= x && x < arr[mid]) ?
        search(arr, left, mid - 1, x) :
        search(arr, mid + 1, right, x);

    // - правая половина упорядочена
    } else if (arr[left] > arr[mid]) {

      return (arr[mid] < x && x < arr[right]) ?
        search(arr, mid + 1, right, x) :
        search(arr, left, mid - 1, x);

    // - левая половина состоит из повторов
    } else if (arr[left] === arr[mid]) {
      // если правая половина отличается — продолжим там поиск
      if (arr[mid] !== arr[right]) {
        return search(arr, mid + 1, right, x);
      }
      // иначе нужно искать в обеих половинах
      const result = search(arr, left, mid - 1, x);
      if (result === -1) {
        return search(arr, mid + 1, right, x);
      }
      return result;
    }
    return -1;
  }  
}());