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

Алгоритмы поиска значения в массиве данных могут не иметь никаких особых требований к входным данным, и такие алгоритмы мы сравним между собой. Если же о входных данных заранее кое-что известно (например, что они упорядочены по алфавиту), то для таких данных могут быть применены другие, более быстродействующие алгоритмы.

Итак, по порядку от самого простого для понимания, с иллюстрацией кодом на  JavaScript. Для всех алгоритмов A — массив входных данных, n — его длина, x — значение, которое хотим найти. Нас будет интересовать индекс элемента массива, имеющего искомое значение. Если результат не найден, то возвращается специальное значение «NOT FOUND».

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

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

Реализация на JavaScript:

// алгоритм
function linearSearch(A,n,x){
    var answer = 'not found';
    for (var i=0; i<n; i++){
        if (A[i]==x){
            answer = i;
        }
    }
    return answer;
}
                       
// инициализация
var A = [1,4,6,8,9,54,2,43];
var n = A.length;
var x = 2;
//тест
var res = linearSearch(A,n,x);
alert (res);

Так как алгоритм всегда проходит n итераций, соответственно, можно сказать, что его быстродействие θ(n). (смотри статью про асимптотические нотации).

Усовершенстованный линейный поиск

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

// алгоритм
function linearSearch(A,n,x){
    for (var i=0; i<n; i++){
        if (A[i]==x){
            return i;
        }
    }
    return 'Not found';
}
                       
// инициализация
var A = [1,4,6,8,9,54,2,43];
var n = A.length;
var x = 2;
//тест
var res = linearSearch(A,n,x);
alert (res);

Поскольку здесь мы не всегда пробегаем по всем значениям, то быстродействие алгоритма (по-научному -его асимптотическая сложность) очень разнится для самого плохого и самого хорошего случаев — от θ(1) до θ(n). Можно сказать, что алгоритм имеет O(n).

Линейный поиск со сторожем (sentinel)

Здесь идея в том, что мы сохраняем последний элемент массива во временной переменной, чтобы на его место записать искомое значение. Это нужно, чтобы вместо цикла for использовать while без риска получить зацикливание, если в массиве не окажется искомой величины. В целом, все эти пляски подразумевают сокращение сравнений в каждой итерации с двух до одного. В описанных выше алгоритмах нам нужно проверить i<n, а затем A[i]=x. В данном же алгоритме проверка одна. Дает ли это выигрыш — зависит от конкретного языка программирования и процессора.

// алгоритм
function linearSearchWithSentinel(A,n,x){
  var last = A[n-1];
  var i =0;
  A[n-1] = x;
    while (A[i]!=x){
      i++;
    }
  A[n] = last;
  if (i<n || A[n]==x){
    return i;
  }else{
    return 'Not found';
  }
}
                       
// инициализация
var A = [1,4,6,8,9,54,2,43];
var n = A.length;
var x = 2;
//тест
var res = linearSearchWithSentinel(A,n,x);
alert (res);

Цена одной итерации здесь может быть ниже, чем у улучшенного линейного поиска, но в асимтотической нотации всё то же самое: от θ(1) до θ(n) и O(n).

Рекурсивный линейный поиск

Тут всё то же самое, только с использованием рекурсии. Просто для иллюстрации.

// алгоритм
function linearSearch(A,n,i,x){
  if (i>n){
    return 'Not found';
  }else if (A[i]==x){
    return i;
  }else{
    return (linearSort(A,n,i+1,x))
  }
}
                       
// инициализация
var A = [1,4,6,8,9,54,2,43];
var n = A.length;
var x = 2;
//тест
var res = linearSearch(A,n,0,x);
alert (res);

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

Этот алгоритм подразумевает, что входной массив уже отсортирован (например, по алфавиту). Только в этом случае можно применять двоичный поиск. Здесь в каждой итерации массив делится на две части, и мы сравниваем срединное значение с искомым. Соответственно, принимаем решение, что может находиться только в левой или только в правой части массива (оказалось больше или меньше границы раздела). Отсекаем ту часть, в которой искомого значения быть не может, таким образом, сразу же уменьшая количество итераций в два раза. Так делаем на каждой следующей итерации, пока «граничное» значение не окажется тем, что мы ищем.

Реализация на JavaScript:

// алгоритм
function binarySearch(A,n,x){
  var p=0, r=n-1, q;
  while (p<=r){
    q = Math.floor((p+r+1)/2);
    if (A[q]==x){
      return q;
    }else if (A[q]>x){
      r=q-1;
    }else{
      p=q+1;
    }
  }
  return 'Not found';
}
                       
// инициализация
var A = [1,4,6,8,9,54,522,4309];
var n = A.length;
var x = 522;
//тест
var res = binarySearch(A,n,x);
alert (res);

Быстродействие (асимптотическая сложность) этого алгоритма O(lb(n)). Здесь lb(n) — это логарифм по основанию 2 (двоичный логарифм).

Рекурсивный двоичный поиск

То же самое, но с применением рекурсии:

// алгоритм
function binarySearch(A,p,r,x){
  var q;
  if (p>r){
    return 'Not found';
  }
  q = Math.floor((p+r+1)/2);
  if (A[q]==x){
    return q;
  }else if (A[q]>x){
    binarySearch(A,p,q-1,x);
  }else{
    binarySearch(A,q+1,r,x);
  }
  
}
                       
// инициализация
var A = [1,4,6,8,9,54,522,4309];
var n = A.length;
var x = 522;
//тест
var res = binarySearch(A,0,n-1,x);
alert (res);