Last active
December 21, 2016 20:22
-
-
Save vividhsv/25e71b2449bc226e528d45850132032a to your computer and use it in GitHub Desktop.
Binary Search
The binary search is used to find an item in an ORDERED list.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def binary_search(item, arr): | |
| def _binary_search(item, first, last, arr): | |
| if last < first: | |
| return False | |
| if last == first: | |
| return arr[last] == item | |
| mid = (first + last) // 2 | |
| if arr[mid] > item: | |
| last = mid | |
| return _binary_search(item, first, last, arr) | |
| elif arr[mid] < item: | |
| first = mid + 1 | |
| return _binary_search(item, first, last, arr) | |
| else: | |
| return arr[mid] == item | |
| return _binary_search(item, 0, len(arr) - 1, arr) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment