Я занимаюсь вопросами подготовки к собеседованию и столкнулся с этой проблемой: Поиск элемента в отсортированном и повернутом массиве.Усовершенствованный двоичный поиск
Самым очевидным решением для меня является 1) найти точку опоры (где число больше, чем следующий номер) и 2) использование, что в качестве точки разделения, чтобы знать, какая половина развернутый и отсортированный массив для выполнения двоичного поиска.
Я нашел «лучшее» (или так утверждают, что у них есть выродки для вундеркиндов). Чтобы не утомлять вас кодом, вот идея высокого уровня. Мой вопрос: Я не понимаю, как найти среднюю точку, давайте искать только за один проход. Является ли это честно лучше, чем исходное решение, с которым я столкнулся?
Высокий уровень "улучшенный/лучше" подход:
1) Find middle point mid = (l + h)/2
2) If key is present at middle point, return mid.
3) Else If arr[l..mid] is sorted
a) If key to be searched lies in range from arr[l]
to arr[mid], recur for arr[l..mid].
b) Else recur for arr[mid+1..r]
4) Else (arr[mid+1..r] must be sorted)
a) If key to be searched lies in range from arr[mid+1]
to arr[r], recur for arr[mid+1..r].
b) Else recur for arr[l..mid]
https://en.wikipedia.org/wiki/Quicksort - http://bl.ocks.org/andrewringler/raw/3809399/ –
Это может помочь вам определить, что вы подразумеваете под «отсортированным и повернутым массив «. Основываясь на аналогичном вопросе, который я нашел в Интернете, я думаю, вы имеете в виду массив, который был отсортирован и с тех пор повернут. Например. [4, 5, 1, 2, 3]. Это то, что вы имели ввиду? – smarx
Если я понимаю ваше решение, это O (n), так как вам нужно отсканировать массив, чтобы найти точку поворота. Если вы все равно собираетесь сканировать массив, вы можете просто искать элемент при этом. Таким образом, ваш подход не лучше, чем просто проверка каждого элемента по одному. – smarx