Binary search can be used to efficiently search for an element in a sorted list. This is an example of recursive approach written in Python 2.7.

Procedure:

Step -1: The program starts by looking at the middle element of the ordered list. If that is the element we are looking for (let’s call it target_element) , the program returns ‘True’

Step – 2: If Step-1 fails, we check if the target_element is smaller than the middle element. If yes, we search for the target_element in the left half of the initial list

Step – 3: If Step-2 fails, we search for the target_element in the right half of the initial list

Input:

This program takes as input a string of space separated sorted integers in ascending order and the target_element that is to be searched for in the list.

Output:

Returns ‘True’ if the target_element is present in the list, else returns ‘False’

Tracing the process:

In-order to trace the control flow, the program can be executed as follows:

python -m trace –trace binary_search_ordered_list.py

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#!/usr/bin/python2 """ Script title: binary_search_ordered_list.py @author: Vasanthi Vuppuluri Date created: April 8, 2015 """ """ Purpose: -------- - To recursively search for an item in an ordered list using Binary search """ def binary_search_on_ordered_list(ordered_list, _list_item): if len(ordered_list) == 0: return False else: _mid_position = len(ordered_list) // 2 if ordered_list[_mid_position] == _list_item: return True else: if ordered_list[_mid_position] > _list_item: return binary_search_on_ordered_list(ordered_list[:_mid_position], _list_item) else: return binary_search_on_ordered_list(ordered_list[_mid_position + 1:], _list_item) def main(): ordered_list = map(int, raw_input("Enter a string of space seperated sorted(ascending) numbers: ").split()) _list_item = int(raw_input("Enter the number you want to search for in the list: ")) print binary_search_on_ordered_list(ordered_list, _list_item) if __name__ == "__main__": main() |

## Leave a Reply