Created
August 25, 2024 16:57
-
-
Save Momellouky/85aee894ca90754b5caffb9001f27ba7 to your computer and use it in GitHub Desktop.
binary search on an ordered array
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(data, param) -> bool : | |
| found = False # To handle recursive calls | |
| if len(data) == 0 : | |
| return None | |
| if len(data) == 2 : | |
| if data[0] == param or data[1] == param : | |
| return True | |
| start_index = 0 | |
| end_index = len(data) - 1 | |
| middle_index = (start_index + end_index) // 2 # integer division | |
| middle_el = data[middle_index] | |
| if param == middle_el : | |
| return True | |
| if param < middle_el : | |
| # the element resides in the first half of the array | |
| found = binary_search(data[0:middle_index + 1], param) | |
| else : | |
| # The element resides in the second half of the array | |
| found = binary_search(data[middle_index:end_index + 1], param) | |
| return found | |
| if __name__ == '__main__' : | |
| # data = [ 7, 10, 3, 1, 66, 6 ] | |
| data = [ 2, 5, 8, 10, 55, 100, 150, 300, 350, 380 ] | |
| param = 100 # The integer we are looking for in the array | |
| found = binary_search(data, param) | |
| if found : | |
| print(f"Element {param} found") | |
| else : | |
| print(f"Element not {param} found") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment