Just my notes on the book

Revision en3, by markodesu, 2023-06-08 17:10:52

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. Too high? 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

Tags binary search, algorithms, logic

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English markodesu 2023-06-08 17:16:06 57
en3 English markodesu 2023-06-08 17:10:52 10 Tiny change: 'll be 63. Next, we ' -> 'll be 63. Too high? Next, we '
en2 English 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 English markodesu 2023-06-08 16:19:50 975 Initial revision (published)