Last active
April 10, 2017 14:47
-
-
Save sethschori/4e526ec07fa30d58fd9bb6b11ef09245 to your computer and use it in GitHub Desktop.
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
| import math | |
| def binary_search(array, target, left=None, right=None): | |
| # Recursively finds target within a sorted array using binary search. | |
| # Returns position of target or -1 if not found. | |
| if left is None: | |
| left = 0 | |
| # If BinarySearch called without right value, set right to final index. | |
| if right is None: | |
| right = len(array) - 1 | |
| # right < left means that target was not found. | |
| if right < left: | |
| return -1 | |
| # According to Wikipedia, this calculation of middle avoids overflow errors | |
| # for very large arrays. | |
| middle = left + math.floor((right - left) / 2) | |
| if array[middle] == target: | |
| return middle | |
| # Recursively search in the left half of array. | |
| if array[middle] > target: | |
| return binary_search(array, target, left, middle - 1) | |
| # Recursively search in the right half of array. | |
| if array[middle] < target: | |
| return binary_search(array, target, middle + 1, right) | |
| my_array = [3, 7, 8, 9, 14, 17, 21] | |
| print (binary_search(my_array, 17)) # 5 | |
| # (List comprehensions are cool!) | |
| my_array = [x * 2 for x in range(1, 10000)] | |
| print (binary_search(my_array, 14445)) # -1 | |
| print (binary_search(my_array, 14)) # 6 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment