Created
May 29, 2025 02:47
-
-
Save DArmstrong87/ca3023c849bb659598faf81b50f6f423 to your computer and use it in GitHub Desktop.
Binary Search of 4 Billion Integers
This file contains hidden or 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 random | |
| from time import time | |
| def binary_search(int_list: range, number: int) -> tuple[str | None, int]: | |
| """ | |
| Return index and number of iterations of a number in range | |
| RANDOM NUMBER 940_695_391 | |
| Time to complete: 0.0069141387939453125ms | |
| INDEX OF RANDOM NUMBER, ('940_695_391', 31) | |
| """ | |
| start_time = time() | |
| low = 0 | |
| high = len(int_list) - 1 | |
| iterations = 1 | |
| while low <= high: | |
| mid = (low + high) // 2 | |
| found_number = int_list[mid] | |
| if found_number == number: | |
| end_time = time() | |
| time_in_ms = (end_time - start_time) * 1_000 | |
| print(f"Time to complete: {time_in_ms}ms", ) | |
| return format(mid, "_"), iterations | |
| if found_number > number: | |
| high = mid - 1 | |
| else: | |
| low = mid + 1 | |
| iterations = iterations + 1 | |
| return None, iterations | |
| max_number = 4_000_000_000 | |
| my_list = range(0, max_number) | |
| random_integer = random.randint(0, max_number) | |
| print("RANDOM NUMBER", format(random_integer, '_')) | |
| print("INDEX OF RANDOM NUMBER,", binary_search(my_list, random_integer )) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment