### markodesu's blog

By markodesu, history, 4 months ago,

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. We get 75. Too high ? Lower it using the same procedure. 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

• +18

 » 4 months ago, # |   0 Auto comment: topic has been updated by markodesu (previous revision, new revision, compare).
 » 4 months ago, # |   0 Auto comment: topic has been updated by markodesu (previous revision, new revision, compare).
 » 4 months ago, # |   0 Auto comment: topic has been updated by markodesu (previous revision, new revision, compare).