Алгоритмы поиска

Линейный поиск

function m1(arr,target){
   for(let i in arr){
       if(i==target){
           return i;
       }
   }
   return -1;
}

let arr = [12,3,4,54,6,77,8];
let target = 6;

console.log(m1(arr,target));

Временная сложность линейного поиска

Временная сложность линейного поиска в лучшем случае

Если наше целевое значение находится в начале массива, алгоритм всегда будет работать с постоянным временем, O(1).

Временная сложность линейного поиска в наихудшем случае

Если наша цель — последний элемент в массиве, то алгоритм должен будет сделать n сравнений (n — длина входного массива). Это означает, что нотация Big O линейного поиска — это Big O(n) — линейная временная сложность.

Временная сложность линейного поиска в среднем случае

Если наш целевой элемент находится где-то в середине массива, то временная сложность будет примерно O(n/2), что упрощается до O(n) — линейное время.

Пространственная сложность линейного поиска

Линейный поиск имеет пространственную сложность O(1) — постоянное пространство. Он не использует никаких вспомогательных структур данных для поиска целевого значения.

Когда использовать линейный поиск

Линейный поиск — лучшее, что мы можем сделать при поиске в несортированных массивах, таких как [2, 3, 1].

Двоичный поиск

Двоичный поиск — это поисковый алгоритм для нахождения позиции элемента в отсортированном массиве.

В этом подходе элемент всегда ищется в середине части массива.

Бинарный поиск можно реализовать только в отсортированном списке элементов. Если элементы еще не отсортированы, нам нужно сначала отсортировать их.

Алгоритм бинарного поиска может быть реализован двумя способами, которые обсуждаются ниже.

1. Итерационный метод
2. Рекурсивный метод

let arr = [12,13,14,15];

function m1(arr,target){
    let min = 0;
    let max = arr.length;
    
    for(let i in arr){
        let mid = Math.floor((max+min)/2);
        
        if(arr[mid]==target){
            return mid;
        }
        
        if(arr[mid] < target){
            min = mid + 1;
        }else if(arr[mid] > target){
            max = mid - 1;
        }
    }
    return -1;
}

console.log(m1(arr,15));

Бинарный поиск — это алгоритм быстрого поиска со сложностью времени выполнения Ο(logn).

Алгоритм поиска работает по принципу разделяй и властвуй. Для правильной работы этого алгоритма сбор данных должен быть в отсортированном виде.

Двоичный поиск ищет конкретный элемент, сравнивая самый средний элемент коллекции. Если совпадение происходит, возвращается индекс элемента. Если средний элемент больше, чем элемент, то элемент ищется в подмассиве слева от среднего элемента. В противном случае элемент ищется в подмассиве справа от среднего элемента. Этот процесс продолжается и в подмассиве, пока размер подмассива не уменьшится до нуля.

Псевдокод бинарного поиска

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

Сортировка массива в JavaScript

let data = [12,34,13,1,434,6,56];

data = data.sort(function(a,b){return a-b});

console.log(data);

Двоичный поиск по ответу

это концепция, в которой мы реализуем бинарный поиск в несортированном массиве