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:

1. Let min = 0 and max = n-1.

2. If max < min, then stop: target is not present in array. Return -1.

3. Compute guess as the average of max and min, rounded down (so that it is an integer).

4. If array[guess] equals target, then stop. You found it! Return guess.

5. If the guess was too low, that is, array[guess] < target, then set min = guess + 1.

6. Otherwise, the guess was too high. Set max = guess - 1.

7. 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))