Binary Search
Question:
Write a program to sort the list [58,6,78,12,333] using binary search and return index position of 12
Program:
|
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 |
import math def bin_search(li, element): bottom = 0 top = len(li)-1 index = -1 while top>=bottom and index==-1: mid = top+bottom/2 if li[mid]==element: index = mid elif li[mid]>element: top = mid-1 else: bottom = mid+1 return index li=[58,6,78,12,333] print bin_search(li,12) |
Explanation:
Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
Output:
|
1 |
3 |
Do share your feedback in comments to help us adding more programs like this.
Leave a Reply