Just my notes on the book

Правка en2, от markodesu, 2023-06-08 16:24:46

Binary search logic:

Suppose there is a set of numbers of 100 count. And I want to guess a number I'd start right in the middle that'd be 50. Then, if the guess is too low I'd take the remaining 50 and divide it by two and add it to the 50. It'll be 63. Next, we do the same procedure and get 57. We'll go like this till we guess right.

To count max numbers of trials we take n=100 and use logarithms. The answer will be log100 (base2) = 7 (6.64)

in python, it would look like this:

def binary_search(list, item):

low = 0

high = len(list)-1

while low <= high:

    mid = (low + high)

    guess = list[mid]

    if guess == item:

        return mid

    if guess > item:

        high = mid - 1

    else:

        low = mid + 1

 return None

my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3)) # => 1

print(binary_search(my_list, -1)) # => None

Теги binary search, algorithms, logic

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский markodesu 2023-06-08 17:16:06 57
en3 Английский markodesu 2023-06-08 17:10:52 10 Tiny change: 'll be 63. Next, we ' -> 'll be 63. Too high? Next, we '
en2 Английский markodesu 2023-06-08 16:24:46 10 Tiny change: ' till we get 1.\n\nTo co' -> ' till we guess right.\n\nTo co'
en1 Английский markodesu 2023-06-08 16:19:50 975 Initial revision (published)