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

Самый простой алгоритм - циклически проходим по элементам массива (среза), сравнивая каждый элемент с искомым.
Алгоритмическая сложность - линейная O(N).

Пример на Go

package main

import "fmt"

func search(data []int, search int) int {
   for i := range data {
      if data[i] == search {
         return i
      }
   }

   return -1
}

func main() {
   testData := []int{7, 2, -5, 3, 1, 9, 8}

   fmt.Println(search(testData, 9)) // 5
   fmt.Println(search(testData, 4)) // -1
}

Пример на PHP

function search(array $data, int $search): int
{
    for ($i = 0; $i < count($data); $i++) {
        if ($data[$i] === $search) {
            return $i;
        }
    }

    return -1;
}

$testArray = [7, 2, -5, 3, 1, 9, 8];

echo search($testArray, 9) . PHP_EOL; // 5
echo search($testArray, 4) . PHP_EOL; // -1

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

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

Пример на Go

package main

import "fmt"

func search(data []int, search int) int {
   minIndex := 0
   maxIndex := len(data) - 1

   for minIndex <= maxIndex {
      middleIndex := (minIndex + maxIndex) / 2

      if search < data[middleIndex] {
         maxIndex = middleIndex - 1 // Отбрасываем правую часть
      } else if search > data[middleIndex] {
         minIndex = middleIndex + 1 // Отбрасываем левую часть
      } else {
         return middleIndex
      }
   }

   return -1
}

func main() {
   testData := []int{-4, -2, 0, 1, 4, 6, 7, 11}

   fmt.Println(search(testData, 6))  // 5
   fmt.Println(search(testData, -3)) // -1
}

Пример на PHP

function search(array $data, int $search): int
{
    $minIndex = 0;
    $maxIndex = count($data) - 1;

    while ($minIndex <= $maxIndex) {
        $middleIndex = intval(($minIndex + $maxIndex) / 2);

        if ($search < $data[$middleIndex]) {
            $maxIndex = $middleIndex - 1; // Отбрасываем правую часть
        } else if ($search > $data[$middleIndex]) {
            $minIndex = $middleIndex + 1; // Отбрасываем левую часть
        } else {
            return $middleIndex;
        }
    }

    return -1;
}

$testArray = [-4, -2, 0, 1, 4, 6, 7, 11];

echo search($testArray, 6) . PHP_EOL;  // 5
echo search($testArray, -3) . PHP_EOL; // -1

Интерполяционный поиск

Работает только с отсортированными массивами (срезами). Данный алгоритм похож на бинарный за одним исключением - он пытается угадать расположение элемента.
Алгоритмическая сложность - логарифмическая O(N) - наихудшая, O(log(log N)) - ожидаемая.

Пример на Go

package main

import "fmt"

func search(data []int, search int) int {
   minIndex := 0
   maxIndex := len(data) - 1

   for data[minIndex] <= search && data[maxIndex] >= search {
      middleIndex := minIndex + ((search-data[minIndex])*(maxIndex-minIndex))/(data[maxIndex]-data[minIndex])

      if search < data[middleIndex] {
         maxIndex = middleIndex - 1 // Отбрасываем правую часть
      } else if search > data[middleIndex] {
         minIndex = middleIndex + 1 // Отбрасываем левую часть
      } else {
         return middleIndex
      }
   }

   return -1
}

func main() {
   testData := []int{-4, -2, 0, 1, 4, 6, 7, 11}

   fmt.Println(search(testData, 7))  // 6
   fmt.Println(search(testData, -3)) // -1
}

Пример на PHP

function search(array $data, int $search): int
{
    $minIndex = 0;
    $maxIndex = count($data) - 1;

    while ($minIndex <= $maxIndex) {
        $middleIndex = $minIndex + intval((($search - $data[$minIndex]) * ($maxIndex - $minIndex)) / ($data[$maxIndex] - $data[$minIndex]));

        if ($search < $data[$middleIndex]) {
            $maxIndex = $middleIndex - 1; // Отбрасываем правую часть
        } else if ($search > $data[$middleIndex]) {
            $minIndex = $middleIndex + 1; // Отбрасываем левую часть
        } else {
            return $middleIndex;
        }
    }

    return -1;
}

$testArray = [-4, -2, 0, 1, 4, 6, 7, 11];

echo search($testArray, 7) . PHP_EOL;  // 6
echo search($testArray, -3) . PHP_EOL; // -1

Источники:
https://en.wikipedia.org/wiki/Linear_search
https://en.wikipedia.org/wiki/Binary_search_algorithm
https://en.wikipedia.org/wiki/Interpolation_search