Binary Search Python Program

What is binary search ?

• Binary search is used only on a sorted collection of elements.
• Most commonly used techniques that is used to solve problems.
• Number of iterations can be reduced in binary search on the basis of the value that is being searched.

Example, consider sorted collection of elements

Binary search: reduces the number of iterations to search the particular element (only 3 iterations in below example).

Binary Search Time complexity

Binary Search Python Program

#!/usr/bin/python                                                               
                                                                                
def binary_search(search_key, list_vals):                                       
    low_index = 0;                                                              
    high_index = len(list_vals);                                                
    while(low_index <= high_index):                                             
        mid_index = (low_index + high_index)/2;                                 
        if (list_vals[mid_index] < search_key):                                 
            low_index = mid_index + 1;                                          
        elif (list_vals[mid_index] > search_key):                               
            high_index = mid_index - 1;                                         
        else:                                                                   
            return mid_index;                                                   
    return -1;                                                                  
                                                                                
if __name__ == "__main__":                                                      
    list_vals = [10, 20, 30, 40, 50, 60, 70, 80];                               
    key = int(raw_input("Please enter a string:"));                             
    print("key is found at index: %d" % binary_search(key, list_vals)); 

$ python binary-search.py 
Please enter a string:30
key is found at index: 2
$ python binary-search.py 
Please enter a string:40
key is found at index: 3
$ python binary-search.py 
Please enter a string:3
key is found at index: -1

Linear Search Python Program using recursive function

#!/usr/bin/python                                                               
                                                                                
def binary_search(low_index, high_index, search_key, list_vals):                
    if(low_index <= high_index):                                                
        mid_index = (low_index + high_index)/2;                                 
        if (list_vals[mid_index] < search_key):                                 
            low_index = mid_index + 1;                                          
        elif (list_vals[mid_index] > search_key):                               
            high_index = mid_index - 1;                                         
        else:                                                                   
            return mid_index;                                                   
        return binary_search(low_index, high_index, search_key, list_vals);     
    # key is not found in the list.                                             
    return -1;                                                                  
                                                                                
if __name__ == "__main__":                                                      
    list_vals = [10, 20, 30, 40, 50, 60, 70, 80];                               
    key = int(raw_input("Please enter a string:"));                             
    low_index = 0;                                                              
    high_index = len(list_vals);                                                
    print("key is found at index: %d" % binary_search(low_index, high_index, key, list_vals));
  

$ python binary-search.py 
Please enter a string:30
key is found at index: 2
$ python binary-search.py 
Please enter a string:40
key is found at index: 3
$ python binary-search.py 
Please enter a string:3
key is found at index: -1