Эта статья была впервые опубликована вВу Ву Шао Тяньюй.com/article/5EC…
Цель состоит в том, чтобы прояснить, что вы знаете
1 Как выглядит базовая дихотомия
Сценарии использования дихотомии на самом деле довольно ограничены, наиболее очевидными особенностями являются:
- В большинстве случаев цель поиска имеет монотонные свойства (монотонно возрастающая, монотонно убывающая)
- Есть верхняя и нижняя границы, и лучше иметь возможность доступа к элементам через индексные индексы.
1.1 С нуля, базовое использование дихотомии
Начнем с простейшего монотонно возрастающего массива, а задача заключается в следующем:
Найти 4 в [1, 2, 3, 4, 5, 6, 7, 8, 9], если существует, вернуть индекс, если не существует, вернуть -1, что требует сложности алгоритма O(logn)
См. выше эту тему, O (logn) необходимая сложность, первая реакция - использовать бинарный поиск, как это сделать?
Сначала смоделируйте примерный процесс следующей дихотомии на диаграмме:
Согласно схеме код выглядит следующим образом:
function searchNum (target, nums) {
if (!nums.length) return -1
let left = 0
let right = nums.length - 1
let mid
while (left <= right) {
// >> 1 位运算代替 除2 取整 操作
// 为什么不写成 mid = (left+right)/2 ,因为考虑到left+right的溢出边界情况
mid = left + ((right - left) >> 1)
if (nums[mid] === target) {
return mid
}
if (nums[mid] < target) {
left = mid + 1
}
if (nums[mid] > target) {
right = mid - 1
}
}
return -1
}
1.2 Кратко опишите процедуру дихотомии
Из приведенных выше вопросов мы можем увидеть рутину точечной дихотомии, У дихотомии есть закон, которому нужно следовать, и можно вывести основной шаблон:
let left = start
let right = end
let mid
while (left <= right) {
mid = (left + right) / 2
if (array[mid] === target) {
return result 或者 break down
}
if (array[mid] < target) {
left = mid + 1
}
if (array[mid] > target) {
right = mid - 1
}
}
После того, как мы получим базовый шаблон дихотомии, мы можем решить ее.квадратный корень хТема такого типа
прикреплятьквадратный корень из хКод решения проблемы:
const mySqrt = function(x) {
if (x < 2) return x
let left = 1, mid, right = Math.floor(x / 2);
while (left <= right) {
mid = Math.floor(left + (right - left) / 2)
if (mid * mid === x) return mid
if (mid * mid < x) {
left = mid + 1
}else {
right = mid - 1
}
}
return right
}
2 Расширение дихотомии
Как упоминалось выше, одним из свойств дихотомий является очевидная монотонность. Вот тут-то и появляется наш шаблон дихотомии, но всегда есть особые случаи.
2.1 Вращающаяся серия массива I
Ссылка на тему:Найти минимальное значение в повернутом отсортированном массиве
Описание темы:
Предположим, что массив, отсортированный в порядке возрастания, вращается в какой-то заранее неизвестной точке. (Например, массив [0,1,2,4,5,6,7] может стать [4,5,6,7,0,1,2] ). Найдите среди них наименьший элемент. Можно предположить, что в массиве нет повторяющихся элементов.
Анализ решения:
- 1. Решить методом грубой силы, пройтись по массиву, записать минимальное значение, временная сложность O(N), N - размер заданного массива
- 2. Дихотомия, временная сложность O(logN),
Как здесь использовать два барементса? Как использовать двухточечные характеристики? Как улучшить непротиворечивый двухточечный метод?
2.1.1 Сорвите оболочку вращающейся решетки и проанализируйте ее законы
Во-первых, давайте разберем тему.Предпосылки для темы:Сортировка по возрастанию,Какой-то момент в ротации неизвестного, в этом случае мы должны сначала рассмотреть, как определить, является ли массив окончательно升序排列еще已经被旋转打乱顺序? Сначала нарисуем картинку:
По приведенному выше рисунку мы можем интуитивно увидеть правило, как судить, нарушено ли оно вращением? Предпосылкой для нормального восходящего порядка являетсяfirst element < last element, а условие выхода из строя:first element > last element
Тогда продолжайте раскапывать закон неупорядоченных массивов, то есть порядок в беспорядке, как его понимать?
Вы нашли это? На левой и правой стороне черной пунктирной линии в качестве разделительной точки они находятся в порядке возрастания, а разделительная точка, в которой расположена черная пунктирная линия, то одна, указанная красной стрелкой.Point, мы можем понимать это как分界点, используемый для разделения двух возрастающих массивов.
Таким образом, мы можем обобщить следующие правила:
- 1. Левый элемент демаркационной точки >= первый элемент
- 2. Правый элемент демаркационной точки
Вернуться к самому вопросу, наша отправная точка - найти минимальное значение в массиве. Теперь, что мы можем найти? мы можем найти分界点,分界点Нашел, минимальное значение находится рядом с точкой деления, а минимальное значение находится попутно.
Ключ к проблеме найден, как найти точку разделения?
Идеи:
Шаг 1: Основываясь на идее дихотомии, сначала найдите середину
Шаг 2: Если mid > first element , что это значит? Это означает, что левая часть середины находится в порядке возрастания, а минимальное значение определенно не находится слева от середины.На данный момент нам нужно найти его справа от середины, поэтому слева = середина + 1
Шаг 3: Если mid
Шаг четвертый: Какие условия завершения? Обсудите два случая:
- 1. Если mid > mid + 1, то mid + 1 является минимальным значением, и возвращается результат
- 2. Если mid
Общая идея ясна, код прост:
const findMin = function (nums) {
if(!nums.length) return null
if(nums.length === 1) return nums[0]
let left = 0, right = nums.length - 1, mid
// 此时数组单调递增，first element就是最小值
if (nums[right] > nums[left]) return nums[0]
while (left <= right) {
mid = left + ((right - left) >> 1)
if (nums[mid] > nums[mid + 1]) {
return nums[mid + 1]
}
if (nums[mid] < nums[mid - 1]) {
return nums[mid]
}
if (nums[mid] > nums[0]) {
left = mid + 1
} else {
right = mid - 1
}
}
return null
}
2.2 Массив вращения серии II
Ссылка на тему:Поиск ротационного сортировки арки
Описание темы:
Предположим, что массив, отсортированный в порядке возрастания, вращается в какой-то заранее неизвестной точке. (Например, массив [0,1,2,4,5,6,7] может стать [4,5,6,7,0,1,2] ). Поиск заданного целевого значения и возврат его индекса, если целевое значение существует в массиве, иначе -1. Можно предположить, что в массиве нет повторяющихся элементов. Временная сложность вашего алгоритма должна быть на уровне O(log n).
Временная сложность алгоритма должна быть на уровне O(log n), бинарный поиск.
Эта проблема, очень похожая на описанную выше, относится к типу проблем. Существует много решений этой проблемы. Ниже приведены два наиболее распространенных:
- 1. По индексу минимального значения 2.1 массив разбивается на два упорядоченных массива, а затем по сравнению между num[0] и target определяется цель.
分界点влево или вправо, а затем выполнить бинарный поиск на соответствующей стороне возрастающего массива - 2. Непосредственно выполнить бинарный поиск по массиву, а затем определить в поиске
分界点пограничное отношение
Если используется метод 2, как определить границу при бинарном поиске?
Из приведенного выше 2.1 можно узнать, что,
Если mid > first element, это означает, что левая часть mid находится в порядке возрастания; если mid
Мы можем сначала написать идею этого вопроса, идея ясна, код прост:
Идеи:
Шаг 1: Основываясь на идее дихотомии, сначала найдите середину
Шаг 2: Определите соотношение размеров между средним и первым элементом и установите интервал, в котором находится средний элемент.
Шаг 3: Обсудите в двух частях:
- В левом восходящем интервале, если цель >= слева и цель
- В восходящем интервале справа, если target > mid и target
- Условие завершения: средний элемент === цель, конец
const search = function(nums, target) {
if (!nums.length) return -1
let left = 0, right = nums.length - 1, mid
while (left <= right) {
mid = left + ((right - left) >> 1)
if (nums[mid] === target) {
return mid
}
if (nums[mid] >= nums[left]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1
} else {
left = mid + 1
}
} else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}
2.3 Массив вращения серии III
Ссылка на тему:Поиск повернутого отсортированного массива II
Описание темы:
Предположим, что массив, отсортированный в порядке возрастания, вращается в какой-то заранее неизвестной точке. (Например, массив [0,0,1,2,2,5,6] может стать [2,5,6,0,0,1,2] ). Напишите функцию, определяющую, существует ли заданное целевое значение в массиве. Возвращает true, если он существует, иначе false.
Эта тема - вариант 2.2, с похожими идеями.
Отличие в том, что здесь массив содержит повторяющиеся элементы, как устранить интерференцию повторяющихся элементов? Например[1,3,1,1,1]Такой массив трудно пройтиmidа такжеleft elementСравнение двух определенных определенных интервалов, но мы можем постоянно сравниватьmidа такжеleftодинаковы для устранения дублирующих помех.
идеи
若 mid element === left element:
此时说明具有重复项目，应该调整left指针，使left向右移动，用以去除重复干扰
Превратите приведенную выше идею в код и добавьте его в 2.2, вы можете получить решение этой проблемы:
const search = function(nums, target) {
if (!nums.length) return false
let left = 0, right = nums.length - 1, mid
while (left <= right) {
mid = left + ((right - left) >> 1)
if (nums[mid] === target) {
return true
}
if (nums[left] === nums[mid]) {
++left
continue
}
if (nums[mid] >= nums[left]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1
} else {
left = mid + 1
}
} else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1
} else {
right = mid - 1
}
}
}
return false
}
Успех AC~
При выполнении: 56 мс, 98,31% пользователей во всех представлении JavaScript
3 Резюме
Выше приведено краткое изложение основных вариантов использования метода дихотомии и основных процедур серии вращающихся массивов.Существует много классических случаев метода дихотомии, которые будут добавлены в будущем.
Личные возможности ограничены, если есть недостатки, я надеюсь указать. 3 кв.