11.9.1 Binary Search Implementation

Function binary_search

• Receives as parameters the array to search (data) and the search key (key)
• First calculates the low end index, high end index and middle index of the portion of the array that the program is currently searching
• Initially, the low end is 0, the high end is the length of the array minus 1 and the middle is the average of these two values
• Loops as long as low is less than or equal to high (the search is not complete) and location is equal to -1 (the key has not yet been found)
• If the value in the middle element is equal to the key, the loop terminates and the function returns location to the caller
• Each iteration of the loop eliminates half of the remaining values in the array

# binarysearch.py
"""Use binary search to locate an item in an array."""
import numpy as np

def binary_search(data, key):
    """Perform binary search of data looking for key."""
    low = 0   # low end of search area
    high = len(data) - 1  # high end of search area
    middle = (low + high + 1) // 2  # middle element index
    location = -1  # return value -1 if not found
    
    # loop to search for element
    while low <= high and location == -1:
        # print remaining elements of array
        print(remaining_elements(data, low, high))

        print('   ' * middle, end='')  # output spaces for alignment 
        print(' * ')  # indicate current middle

        # if the element is found at the middle                    
        if key == data[middle]:                                   
            location = middle  # location is the current middle     
        elif key < data[middle]:  # middle element is too high
            high = middle - 1  # eliminate the higher half          
        else:  # middle element is too low                         
            low = middle + 1  # eliminate the lower half            
                                                                        
        middle = (low + high + 1) // 2  # recalculate the middle

    return location  # return location of search key
                            

Function remaining_elements

• Shows the portion of the array being searched

def remaining_elements(data, low, high):
    """Display remaining elements of the binary search."""
    return '   ' * low + ' '.join(str(s) for s in data[low:high + 1])
    

Function main

def main():
    # create and display array of random values
    data = np.random.randint(10, 91, 15)
    data.sort()
    print(data, '\n')

    search_key = int(input('Enter an integer value (-1 to quit): ')) 

    # repeatedly input an integer; -1 terminates the program
    while search_key != -1:
        location = binary_search(data, search_key)  # perform search

        if location == -1:  # not found
            print(f'{search_key} was not found\n') 
        else:
            print(f'{search_key} found in position {location}\n')

        search_key = int(input('Enter an integer value (-1 to quit): '))

# call main to execte the search 
main()

[13 14 15 17 25 30 32 36 56 61 63 64 65 86 86] 

13 14 15 17 25 30 32 36 56 61 63 64 65 86 86
                      * 
                        56 61 63 64 65 86 86
                                  * 
                                    65 86 86
                                        * 
                                    65
                                     * 
65 found in position 12

13 14 15 17 25 30 32 36 56 61 63 64 65 86 86
                      * 
13 14 15 17 25 30 32
          * 
13 14 15
    * 
      15
       * 
16 was not found

---

©1992–2020 by Pearson Education, Inc. All Rights Reserved. This content is based on Chapter 5 of the book Intro to Python for Computer Science and Data Science: Learning to Program with AI, Big Data and the Cloud.

DISCLAIMER: The authors and publisher of this book have used their best efforts in preparing the book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The authors and publisher make no warranty of any kind, expressed or implied, with regard to these programs or to the documentation contained in these books. The authors and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs.