O(log2n)
для массива из 1000 элементов
O(log21000)
время сортировки массива более длительнее чем работа линейного поиска
требование
массив отсортирован по порядку
Процесс выполнения
смотрим по середине символ
— если символ идет раньше, которую мы открыли, то будем
рассматривать левую часть
— если символ идет позже, которую мы открыли, то будем
рассматривать правую часть
таким образом каждый раз мы отсеиваем ровно половину в массиве пока не найдем элемент
количество итераций — счетчик выполнения оператора for
const arr=[1,4,5,8,51,2,7,5,5,2,11]
let cnt = 0;
function binarySearch(arr, item){
let start = 0
let end = arr.length;
let middle;
let found = false;
let position = -1;
while (found === false && start <= end){
cnt+=1
middle = Math.floor((start+end)/2);
if (arr[middle] === item){
found = true
position = middle
return position;
}
if (item < arr[middle]){
end = middle-1
} else {
start = middle+1
}
return position;
}
console.log(binarySearch(arr,0))
console.log(cnt);
- рекурсивный код более локаничный
cnt=0;
function recursiveBinarySearch(arr,item,start,end){
let middle = Math.floor((start+end)/2);
cnt+=1
if (item == arr[middle]){
return middle;
}
if (item < arr[middle]){
return recursiveBinarySearch(arr,item,start,middle-1)
} else {
return recursiveBinarySearch(arr,item,middle+1,end)
}
}
console.log(recursiveBinarySearch(arr,12,0,arr.length))
console.log(cnt);