Оптимизация поиска в отсортированном списке

Question

Я столкнулся с проблемой, когда мы получаем отсортированный список чисел, и в какой-то момент числа в списке начинают повторяться, что-то вроде 0,1,2,3,4,5,6,7,8,8,8, нам нужно получить позицию, с которой началось повторение.

Ниже приведен подход, который я выбрал ...

function find(arr) {  
  let max = arr.length-1
  let min = 0
  do {
    let iter = Math.round((min + max) / 2)
    if (arr[max] == arr[iter])
      max = iter
    else
      min = iter
  } while (min + 1 < max)
  return max
}

arr = [0,1,2,3,4,5,6,7,8,8,8]
console.log(find(arr))

arr = [0,1,2,2,2,2,2,2,2,2,2]
console.log(find(arr))

arr = [2,4,6,8,10,10]
console.log(find(arr))

Вероятно, существует рекурсивный способ, но я не мог понять это
Есть ли более эффективный способ решить эту проблему?

Answer 1

Как указали Бобра и Рэймонд Чен, вы не можете добиться большего успеха, чем О (войдите n) Тем не менее, вы также спросили о рекурсивном решении. Вот вам go:

function find(arr, min_idx = 0, max_idx = arr.length - 1) {
  if (min_idx >= max_idx)
    return max_idx 
  let guess = Math.floor((min_idx + max_idx) / 2)
  if (arr[guess] == arr[max_idx])
    return  find(arr, min_idx, guess)  
  return find(arr, guess + 1, max_idx)
}

let arr = [0,1,2,3,4,5,6,7,8,8,8]
console.log(find(arr))

arr = [0,1,2,2,2,2,2,2,2,2,2]
console.log(find(arr))

arr = [2,4,6,8,10,10]
console.log(find(arr))

arr = [10,10,10]
console.log(find(arr))

Обратите внимание, что это также исправляет ошибку в вашей реализации. Я добавил тестовый пример, в котором ваш ответ дал неправильный ответ, когда первый элемент был равен макс.

Answer 2

ваше решение имеет O(log N) сложность. Кажется, здесь нет более быстрого алгоритма, чем бинарный поиск. так что ваше решение в порядке