В чем разница между линейным и двоичным поиском?

Question

В чем разница между линейным поиском и бинарным поиском?

Answer 1

Linear Search просматривает элементы, пока не найдет искомое значение.

Эффективность: O(n)

Пример кода Python:

test_list = [1, 3, 9, 11, 15, 19, 29]
test_val1 = 25
test_val2 = 15

def linear_search(input_array, search_value):
    index = 0
    while (index < len(input_array)) and (input_array[index] < search_value):
        index += 1
    if index >= len(input_array) or input_array[index] != search_value:
        return -1

    return index


print linear_search(test_list, test_val1)
print linear_search(test_list, test_val2)

Binary Search находит средний элемент массива. Проверяет, что среднее значение больше или меньше значения поиска. Если он меньше, он получает левую часть массива и находит средний элемент этой части. Если оно больше, получает правую часть массива. Он повторяет операцию, пока не найдет искомое значение. Или, если в массиве нет значения, поиск завершается.

Эффективность: O(logn)

Пример кода Python:

test_list = [1, 3, 9, 11, 15, 19, 29]
test_val1 = 25
test_val2 = 15

def binary_search(input_array, value):
    low = 0
    high = len(input_array) - 1
    while low <= high:
        mid = (low + high) / 2
        if input_array[mid] == value:
            return mid
        elif input_array[mid] < value:
            low = mid + 1
        else:
            high = mid - 1

    return -1


print binary_search(test_list, test_val1)
print binary_search(test_list, test_val2)

Также вы можете увидеть визуализированную информацию о линейном и двоичном поиске здесь: https://www.cs.usfca.edu/~galles/visualization/Search.html