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
collection sorted
Binary search: reduces the number of iterations to search the particular element (only 3 iterations in below example).
linear search

Binary Search Time complexity

Binary search performs the search operation on the other half in every steps. This results in a worst case time complexity of O(log2N), where N is the number of elements in the collection.

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)); 
Output:
$ 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));
  
Output:
$ 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

Privacy Policy  |  Copyright@2017 - All Rights Reserved.  |  Contact us   |  Report website issues in Github   |  Facebook page   |  Google+ page

Email Facebook Google LinkedIn Twitter
^