Created
April 10, 2022 05:42
-
-
Save agung037/94ff1c2c98884b8829ebedafb3fded09 to your computer and use it in GitHub Desktop.
pengujian binary vs linear
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 | |
| import time | |
| def gen_unique_random(): | |
| return random.sample(range(1, 100), 99) | |
| def linear_search(d,t): | |
| for i in d: | |
| if i == t: | |
| return i | |
| return -1 | |
| def binarySearch(arr, l, r, x): | |
| if r >= l: | |
| mid = l + (r - l) // 2 | |
| if arr[mid] == x: | |
| return mid | |
| elif arr[mid] > x: | |
| return binarySearch(arr, l, mid-1, x) | |
| else: | |
| return binarySearch(arr, mid + 1, r, x) | |
| else: | |
| return -1 | |
| # 100000 sample data untuk di cari | |
| data = [gen_unique_random() for x in range(100000)] | |
| target = 50 | |
| # pengujian menggunakan linear | |
| print("Percobaan dengan linear search : ") | |
| for i in range(10): | |
| linear_time = time.time() | |
| for x in data: | |
| linear_search(x, target) | |
| print(i+1, " %s detik " % (time.time() - linear_time)) | |
| # dalam binary search data harus urut | |
| data_urut = [sorted(x) for x in data] | |
| # pengujian menggunakan binary | |
| print("\nPercobaan dengan binary search : ") | |
| for i in range(10): | |
| binary_time = time.time() | |
| for x in data_urut: | |
| binarySearch(x, 0, len(x)-1, target) | |
| print(i+1, " %s detik" % (time.time() - binary_time)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment