Оглавление статьи
- Вводная часть
- Найти элемент в отсортированном массиве
- Нахождение нижней границы
- Нахождение верхней границы
- Поиск позиции для вставки
- Поиск нижней и верхней позиции
- Поиск количества заданного элемента
- Поиск элемента в повернутом массиве
- Поиск минимального элемента в повернутом массиве
- Найти пиковый элемент
- Найти ближайшее число к квадрату
- Поиск степени числа
- Коко ест бананы
- Минимальное количество дней для изготовления букетов
- Найти наименьший делитель
Вводная часть
Бинарный поиск — это эффективный алгоритм поиска, который широко применяется в информатике и программировании. В основе этого метода лежит идея последовательного деления данных пополам, что позволяет быстро находить нужный элемент в упорядоченном массиве или списке.
Найти элемент в отсортированном массиве
Рассмотрим решение задачи на поиск элемента в отсортированном массиве.
Например: [3,4,6,7,9,12,16,17] 7 => 3
const arr = [3,4,6,7,9,12,16,17]
const target = 7
let low = 0
let high = arr.length - 1
let pos = -1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (arr[mid] === target) {
pos = mid
break
} else if (arr[mid] > target) {
high = mid - 1
} else {
low = mid + 1
}
}
// Позиция искомого элемента: 3
console.log('Позиция искомого элемента:', pos)Вариант 2
Через рекурсию.
const arr = [3,4,6,7,9,12,16,17]
const target = 16
// Позиция искомого элемента: 6
console.log('Позиция искомого элемента:', binary(arr, target))
function binary(arr, target) {
const search = (arr, low, high) => {
const mid = Math.floor((low + high) / 2)
if (low > high) {
return -1
}
if (arr[mid] === target) {
return mid
}
if (arr[mid] > target) {
high = mid - 1
} else {
low = mid + 1
}
return search(arr, low, high)
}
return search(arr, 0, arr.length - 1)
}Нахождение нижней границы
Рассмотрим решение задачи на поиск нижней границы в отсортированном массиве.
Например: [3,5,5,5,5,8,8,15,19,19] 8 => 5 позиция
const arr = [3,5,5,5,5,8,8,15,19,19]
const target = 8
let low = 0
let high = arr.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (arr[mid] >= target) {
high = mid - 1
} else {
low = mid + 1
}
}
// Нижняя граница: 5
console.log('Нижняя граница:', low)Нахождение верхней границы
Рассмотрим решение задачи на поиск верхней границы в отсортированном массиве.
Например: [3,5,5,5,5,8,8,15,19,19] => 5 позиция
const arr = [3,5,5,5,5,8,8,15,19,19]
const target = 8
let low = 0
let high = arr.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (arr[mid] > target) {
high = mid - 1
} else {
low = mid + 1
}
}
// Верхняя граница: 6
console.log('Верхняя граница:', high)Поиск позиции для вставки
Рассмотрим решение задачи на поиск позиции где должен был бы располагаться не достающий элемент.
Например: [1,2,4,7] 6 => 3 позиция
const arr = [1,2,4,7]
const target = 6
let low = 0
let high = arr.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (arr[mid] > target) {
high = mid - 1
} else {
low = mid + 1
}
}
// 'Пропущенная позиция: 3'
console.log('Пропущенная позиция:', low)Поиск нижней и верхней позиции
Рассмотрим решение задачи на поиск нижней и верхней позиции где должен был бы располагаться не достающий элемент.
Например: [10,20,30,40,50] 25 => [1, 2]
const arr = [10,20,30,40,50]
const target = 25
let low = 0
let high = arr.length - 1
let floor = -1
let ceil = -1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (arr[mid] >= target) {
high = mid - 1
ceil = mid
} else if (arr[mid] <= target) {
low = mid + 1
floor = mid
}
}
// Позиция от / до
console.log('Позиция от / до:', [floor, ceil])Поиск количества заданного элемента
Рассмотрим решение задачи на поиск количества заданного элемента в массиве.
Например: [2,4,6,8,8,8,8,8,1,1,13] 8 => 5
const arr = [2,4,6,8,8,8,8,8,1,1,13] // 1,1,2,4,6,8,8,8,8,13
const target = 8
let result = [-1, -1]
const start = first(arr, target)
if (start !== -1) result = [start, last(arr, target)]
// Количество элементов: 5
console.log('Количество элементов:', count(result))
function first(arr, target) {
arr.sort((a,b) => a - b)
let low = 0
let high = arr.length - 1
let result = -1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (arr[mid] >= target) {
result = mid
high = mid - 1
} else {
low = mid + 1
}
}
return result
}
function last(arr, target) {
arr.sort((a,b) => a - b)
let low = 0
let high = arr.length - 1
let result = -1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (arr[mid] > target) {
high = mid - 1
} else {
result = mid
low = mid + 1
}
}
return result
}
function count(result) {
if (result[0] === -1) return 0
return result[1] - result[0] + 1
}Поиск элемента в повернутом массиве
Рассмотрим решение задачи на поиск позиции элемента в повернутом массиве.
Например: [7,8,9,1,2,3,4,5,6] 3 => 5
const arr = [7,8,9,1,2,3,4,5,6]
const target = 3
let low = 0
let high = arr.length - 1
let res = -1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (arr[mid] === target) {
res = mid
break
}
if (arr[low] <= arr[mid]) {
if (arr[low] <= target && target <= arr[mid]) {
high = mid - 1
} else {
low = mid + 1
}
} else {
if (arr[mid] <= target && target <= arr[high]) {
low = mid + 1
} else {
high = mid - 1
}
}
}
// Позиция элемента: 5
console.log('Позиция элемента:', res)Поиск минимального элемента в повернутом массиве
Рассмотрим решение задачи на поиск минимального элемента в повернутом массиве.
Например: [7,8,0,1,2,3,4,5,6] => 0
const arr = [7,8,0,1,2,3,4,5,6]
let low = 0
let high = arr.length - 1
let min = arr[0]
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (arr[low] <= arr[high]) {
min = Math.min(min, arr[low])
break
}
if (arr[mid] >= arr[low]) {
min = Math.min(min, arr[low])
low = mid + 1
} else {
min = Math.min(min, arr[mid])
high = mid - 1
}
}
// Минимальный элемент: 0
console.log('Минимальный элемент:', min)Найти пиковый элемент
Рассмотрим решение задачи на поиск позиции пикового элемента.
Например: [1,2,3,4,5,6,7,8,5,1] => 7
const arr = [1,2,3,4,5,6,7,8,5,1]
// Позиция пикового элемента: 7
console.log('Позиция пикового элемента:', find(arr))
function find(arr) {
let n = arr.length
if (n === 1) return 0
if (arr[0] > arr[1]) return 0
if (arr[n-1] > arr[n-2]) return n - 1
let low = 1
let high = n - 2
while (low <= high) {
let mid = Math.floor((low + high) / 2)
if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
return mid
} else if (arr[mid] > arr[mid - 1] ) {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}Найти ближайшее число к квадрату
Рассмотрим решение задачи на поиск ближайшего числа квадрат которого наиболее близок к заданному числу.
Например: 28 => 5 так как 5 * 5 = 25
const n = 28
let low = 1
let high = n
while (low <= high) {
const mid = Math.floor((low + high) / 2)
const val = mid * mid
if (val <= n) {
low = mid + 1
} else {
high = mid - 1
}
}
// Ближайшее число: 5
console.log('Ближайшее число:', high)Поиск числа степени
Рассмотрим решение задачи на поиск числа степени.
Например: X ^ 2 = 16 => 4 так как 4 ^ 2 = 16
const n = 2
const m = 16
// Число в степени 2 дает 16: 4
console.log('Число в степени 2 дает 16:', find(n, m))
function find(n, m) {
let low = 1
let high = m
while (low <= high) {
let mid = Math.floor((low + high) / 2)
let pow = Math.pow(mid, n)
if (pow === m) {
return mid
} else if (pow < m) {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}Коко ест бананы
Рассмотрим решение задачи на поиск количества бананов которые может съесть обезьяна в час.
Например: [3,6,11,7] => 4 банана в час
const arr = [3,6,11,7] // количество бананов
const h = 8 // общее отведенное время на поедание бананов
// Количество бананов в час:
console.log('Количество бананов в час:', koko(arr, h))
function koko(arr, h) {
let low = 1
let high = Math.max(...arr)
let mid = -1
while(low <= high) {
mid = Math.floor((low + high) / 2)
const sum = calculate(arr, mid)
if (sum > h) {
low = mid + 1
} else {
high = mid - 1
}
}
return mid
}
function calculate(arr, max) {
let sum = 0
for (let i = 0; i < arr.length; i++) {
sum += Math.ceil(arr[i] / max)
}
return sum
}Минимальное количество дней для изготовления букетов
Рассмотрим решение задачи на поиск минимального количества дней для изготовления букетов.
Например: [7,7,7,7,13,11,12,7] => на 12 день можно будет сделать 2 букета с 3 розами
const arr = [7,7,7,7,13,11,12,7] // день когда распускается цветок
const m = 2 // букетов
const k = 3 // роз в одном букете
// Букеты можем сделать в день: 12
console.log('Букеты можем сделать в день:', bouquets(arr, m, k))
function bouquets(arr, m, k) {
let low = Math.min(...arr)
let high = Math.max(...arr)
while (low <= high) {
const mid = Math.floor((low + high) / 2)
let bouquet = count(mid)
if (bouquet === m) {
return mid
} else if (bouquet < m) {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}
function count(min) {
let sum = 0
let bouquet = 0
for (let i = 0; i < arr.length; i++) {
if (arr[i] <= min) {
sum++
} else {
bouquet += Math.floor(sum / k)
sum = 0
}
}
bouquet += Math.floor(sum / k)
return bouquet
}Найти наименьший делитель
Рассмотрим решение задачи на поиск наименьшего положительного целочисленного делителя, чтобы при делении на него всех элементов данного массива сумма результата деления была меньше или равна заданному пороговому значению.
Например: [1,2,3,4,5] 8 => 3
const arr = [1,2,3,4,5]
const threshold = 8
// Наименьший делитель: 3
console.log('Наименьший делитель:', smallest(arr, threshold))
function smallest(arr, threshold) {
if (arr.length > threshold) return -1
let low = 1
let high = Math.max(...arr)
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (sum(arr, mid) <= threshold) {
high = mid - 1
} else {
low = mid + 1
}
}
return low
}
function sum(arr, mid) {
let total = 0
for (let i = 0; i < arr.length; i++) {
total += Math.ceil(arr[i] / mid)
}
return total
}