Binary Search
Pseudocode
Here's the pseudocode for binary search, modified for searching in an array. The inputs are the array, which we call array
; the number n
of elements in array
; and target
, the number being searched for. The output is the index in array
of target
:
Here is modified pseudocode for binary search that handles the case in which the target number is not present:
Let
min = 0
andmax = n-1
.If
max < min
, then stop:target
is not present inarray
. Return-1
.Compute
guess
as the average ofmax
andmin
, rounded down (so that it is an integer).If
array[guess]
equalstarget
, then stop. You found it! Returnguess
.If the guess was too low, that is,
array[guess] < target
, then setmin = guess + 1
.Otherwise, the guess was too high. Set
max = guess - 1
.Go back to step 2.
import math
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
def doSearch(array, target_value):
min_value = 0
max_value = len(array) - 1
while min_value <= max_value:
guess = int(math.floor((max_value + min_value) / 2))
if array[guess] == target_value:
return guess
elif array[guess] < target_value:
min_value = guess + 1
else:
max_value = guess - 1
return -1;
target = 73
print(doSearch(primes, target))
Last updated