Рубрики
Массивы "поиск" Алгоритмы

Массивы «Бинарный поиск»

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);
Рубрики
Массивы "поиск" Алгоритмы

Массивы «линейный поиск»

последовательно сравниваем с тем элементом, который ищем

массив из n элементов
O(n)
n - количество итераций в массиве

для массива из 1000 элементов
O(1000)

лучший случай
элемент находим в начале списка за одну операцию

худший случай
элемент находим в конце списка

сложность
нам необходимо пройтись по каждому элементу, который в этом списке находится

const arr=[1,4,5,8,51,2,7,5,5,2,11]
let cnt = 0;//количество итераций
function linearSearch(arr, item){
 for (let i =0; i< arr.length; i++){
  cnt+=1;
  if (arr[i] === item) {
   return i;
  }
 }
 return null;
}
console.log(linearSearch(arr, 11));
console.log('count = ', count);