Поиск в JavaScript

Поиск очень важен в повседневной жизни программиста. Если ваш файл слишком велик и вы хотите найти определенное слово для поиска, вам нужна поисковая система.

Типы поиска в мире программирования:

Существует два типа поиска:

1. Линейный поиск ( Последовательный поиск)
2. Двоичный поиск ( Поиск с половинным интервалом)

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

В программировании линейный поиск ( последовательный поиск ) — это метод поиска элемента в массиве или списке. . Он последовательно проверяет все элементы массива или списка на наличие целевого значения, пока не будет найдено совпадение или не будут найдены все элементы.

Разработка кода:

1. На первом этапе мы создаем функцию, принимающую два параметра, а именно arr и num.
2. После этого мы выполняем for loop над массивом и сравниваем каждое значение массива со значением num.
3. Если мы нашли искомый элемент, то он возвращает значение индекса искомого элемента, иначе возвращает -1

Анализ производительности линейного поиска:

worst-case performance ---- O(n)
best-case performance ---- O(1)
average-case performance ---- O(n)
worst-case space complexity ---- O(1)

Бинарный поиск:

Двоичный поиск также известен как Поиск с половинным интервалом. В алгоритме поиска этого типа мы просто выделяем массив из средней точки. Если средняя точка равна целевому значению, возвращается значение индекса элемента искомого элемента в массиве. Если среднее значение меньше целевого значения, то значение Left равно (mid+1), в противном случае Right равно (mid -1) и выполняется поиск во вложенных массивах. Этот поиск выполняется до тех пор, пока целевое значение не будет найдено или элемент недоступен в списке.

Алгоритм бинарного поиска:

Given an array of A and having n no. of sorted items like A[0] <= A[1] <= A[2] <= .... <= A[n-1] <= A[n] and T is the target value. The below algo find the index of target value in A array.
1. Set Left = 0 and Right = n-1
2. If Left > Right, Binary Search terminates as unsuccessful
3. Set m (middle element) to the floor of (Left + Right)/2
4. If A[m] > T, then set Right to m-1 and go to step 2.
5. If A[m] < T, then set Left to m+1 and go to step 2.
6. If A[m] = T, search is done, return the value of m.

Функциональное преобразование вышеуказанного алгоритма:

function binary_search ( A, n, T ) :
  L = 0
  R = n - 1
  while R > = L
    m = floor((L+R)/2)
    If A[m] > T
      R = m-1
    Else if A[m] < T
      L = m+1
    Else
      return m
  return unsuccessful

Фрагмент кода бинарного поиска:

Доработка приведенного выше фрагмента кода:

1. На первом этапе мы создаем функцию с тремя параметрами, а именно:arr arr.lengthnum
2. После этого присваиваем значениеarr.length переменнойn
3. В следующей строке мы выполняем сортировку в заданном массиве arr .

var sortedArr = arr.sort(function (a, b) {
     return a-b;  
});

4. После этого назначьте 0 налево и n-1 на право.

5. Теперь мы просто помещаем while loopwithleft <=right в цикл while, даем минимальное значение суммы левого и правого значений, а затем делим на 2 среднюю переменную(var mid = Math.floor((left+right)/2)) и мы можем проверить три условия:

1. If the value of sortedArr[m] === num, then return the value of mid.
if(sortedArr[mid] === num) {
         return mid    
      }
2.If sortedArr[mid] > num, then right is mid -1
if (sortedArr[mid] > num) {
  right = mid - 1;
}
3. If sortedArr[mid] < num, then left is mid + 1
else {      
  left = mid + 1;    
}

6. Если left >right, то элемент для поиска отсутствует в списке или массиве.

Бинарный поиск рекурсивным методом:

Основное отличие простой функции бинарного поиска от рекурсивного метода заключается в том, что мы вызываем binary_search_recursive функцию в каждом условии if else .

1. If the value of sortedArr[m] === num, then return the value of mid.
if(sortedArr[mid] === num) {
         return mid    
      }
2.If sortedArr[mid] > num, then right is mid -1
if (sortedArr[mid] > num) {
  right = mid - 1;
  return binary_search_recursive(arr, left, right, num);
}
3. If sortedArr[mid] < num, then left is mid + 1
else {      
  left = mid + 1;   
  return binary_search_recursive(arr, left, right, num); 
}

Анализ производительности бинарного поиска:

worst-case performance ---- O(log n)
best-case performance ---- O(1)
average-case performance ---- O(log n)
worst-case space complexity ---- O(1)

Вывод :

В этой статье рассматривается концепция линейного поиска и бинарного поиска в javascript. Если у вас есть какие-либо сомнения и вы хотите получить от меня какую-либо помощь, напишите мне по адресу [email protected]. В следующем разделе мы рассмотрим методы сортировки в Javascript.

Методы сортировки в JavaScript