Бинарный поиск может быть (одним из) наиболее полезным алгоритмом в повседневной жизни фронтенд-инженера. Ведь git bisect так удобно находить плохой коммит a̶n̶d̶ ̶b̶l̶a̶m̶e̶ ̶p̶e̶o̶p̶l̶e̶.
ЛитКод 278. Первая плохая версия о том, как работает git bisect.
Концепция бинарного поиска довольно прямолинейна, мы в основном сокращаем половину диапазона поиска каждый раз после поиска. Таким образом, временная сложность в худшем случае составляет O (log n).
Зная концепцию, легко написать код самостоятельно, пока вы на самом деле не сделаете это. Вы, вероятно, столкнетесь с некоторыми проблемами, как и я — трудно определить границу. Иногда я становлюсь больше, иногда меньше, иногда попадаю в бесконечный цикл 😥….
А потом я нашел несколько шаблонов для бинарного поиска… например, тот, что в Википедии, весьма полезен.
function binary_search_leftmost(A, n, T): // A is the condition, T is the target
L := 0
R := n
while L < R:
m := floor((L + R) / 2)
if A[m] < T:
L := m + 1
else:
R := m
return L
Это выше может помочь решить большинство проблем бинарного поиска с некоторыми небольшими изменениями, как это…
function binary_search_rightmost(A, n, T):
L := 0
R := n
while L < R:
m := floor((L + R) / 2)
if A[m] <= T:
L := m + 1
else:
R := m
return L - 1
Давайте посмотрим на некоторые проблемы с LeetCode…
Имея отсортированный (в порядке возрастания) целочисленный массив
numsизnэлементов иtargetзначение, напишите функцию для поискаtargetвnums. Еслиtargetсуществует, вернуть его индекс, иначе вернуть-1.
Мы можем использовать шаблон непосредственно в этой задаче.
var search = function(nums, target) {
let left = 0;
let right = nums.length;
while(left < right){
let mid = Math.floor((left+right)/2);
if(nums[mid] < target){
left = mid + 1;
}else{
right = mid;
}
}
return nums[left] === target ? left : -1;
};
Я не копирую сюда описание проблемы, потому что это просто идея git bisect .
var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
let left = 1;
let right = n;
let m;
while(left<right){
m = Math.floor((left + right)/2);
if(isBadVersion(m)) {
right = m;
} else {
left = m + 1;
}
}
return left;
};
};
378. K-й наименьший элемент в отсортированной матрице
Дана матрица n x n, в которой каждая из строк и столбцов отсортирована в порядке возрастания, найдите k-е наименьший элемент матрицы.
Обратите внимание, что это k-й наименьший элемент в отсортированном порядке, а не k-й отдельный элемент.
Очень важно знать, что и строки отсортированы, потому что это говорит нам о том, что наименьшее и наибольшее числа равны matrix[0][0] и matrix[len-1][len-1] .
После того, как мы определили left и right , нам просто нужно найти самое левое число, у которого есть k чисел, меньших или равных ему. Это будет наш окончательный ответ.
var kthSmallest = function(matrix, k) {
let len = matrix.length;
let left = matrix[0][0];
let right = matrix[len-1][len-1];
let m;
while(left < right){
m = Math.floor((left+right)/2);
let lessOrEqualM = 0;
matrix.forEach(row => {
row.forEach(num => {
if(num<=m) lessOrEqualM++;
})
})
if(lessOrEqualM>=k) right = m;
if(lessOrEqualM<k) left = m + 1;
}
return left;
};
Самое интересное в этой задаче заключается в том, что нам не нужно перебирать каждое число в двумерной сетке, потому что результатом будет самое левое число, соответствующее стандарту.
В процессе обучения добавлю больше заметок.
Предложения и комментарии приветствуются. Спасибо!
Следующие ссылки помогли мне лучше понять проблемы…
