27. Расскажите про линейный и бинарный поиск.

Линейный поиск - сложность O(n), так как все элементы проверяются по очерди.

1. Бинарный поиск - O(log(n)). Массив должен быть отсортирован. Происходит поиск индекса в массиве, содержащего искомое значение.
2. Берем значение из середины массива и сраваем с искомым. Индекс середины считается по формуле mid = (high + low) / 2
   low - индекс начала левого подмассива, high - индекс конца правого подмассива.
3. Если значение в середине больше искомого, то рассматриваем левый подмассив и high = middle - 1
4. Если меньше, то правый и low = middle + 1
5. Повторяем, пока mid не страновится равен искомому элементу или подмассив не станет пустым.

public static int binarySearch(int[] a, int key) {
int low = 0;
int high = a.length - 1;

while (low <= high) {
int mid = (low + high)/2;

if (key > a[mid]) {
low = mid + 1;
} else if (key < a[mid]) {
high = mid - 1;
} else return mid;
}
return -1;
}

Предыдущий вопрос: 26. Расскажите про красно-черное дерево.

Следующий вопрос: 28. Расскажите про очередь и стек.

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку: напишите мне