Cho dãy các số A = [3, 1, 0, 10, 13, 16, 9, 7, 11]. a) Viết chương trình mô tả

Câu hỏi số 769243:

Vận dụng

Cho dãy các số A = [3, 1, 0, 10, 13, 16, 9, 7, 11].

a) Viết chương trình mô tả thuật toán tìm kiếm phần tử C = 9 của dãy trên. Tính thời gian chính xác thực hiện công việc tìm kiếm này.

b) Giả sử dãy A ở trên đã được sắp xếp theo thứ tự tăng dần: A = [0, 1, 3, 5, 7, 9, 10, 11, 13, 16]. Viết chương trình tìm kiếm phần tử C = 9 theo thuật toán tìm kiếm nhị phân. Tính thời gian thực hiện thuật toán. So sánh với kết quả tìm kiếm ở câu a.

Quảng cáo

Xem lời giải

Câu hỏi:769243

Giải chi tiết

Chương trình tính thời gian thực tế của thuật toán tìm kiếm tuần tự trên cùng một dãy có thể như sau:

1 from time import perf_counter

2 def LinearSearch(A,K):

3 for i in range(len(A)):

4 if A[i] == K:

5 return i

6 return -1

7 deft BinarySearch(A,K):

8 left = 0

9 right = len(A) – 1

10 while left <= right:

11 mid = (left + right)//2

12 if A[mid] == K:

13 return mid

14 elif A[mid] < K:

15 left = mid + 1

16 else:

17 right = mid – 1

18 return -1

20 A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]

21 K = 9

22 t1 = perf_counter()

23 LinearSearch(A,K)

24 t2 = perf_counter()

25 print("Tìm kiếm tuần tự:", round(t2-t1,50))

26 B = sorted(A)

27 t1 = perf_counter()

28 BinarySearch(B,K)

29 t2 = perf_counter()

30 print("Tìm kiếm nhị phân:", round(t2-t1,50))

Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K9 Chú ý! Lộ Trình Sun 2027 - 1 lộ trình ôn đa kỳ thi (TN THPT, ĐGNL (Hà Nội/ Hồ Chí Minh), ĐGNL Sư Phạm, ĐGTD, ĐGNL Bộ Công an, ĐGNL Bộ Quốc phòngTD - Click xem ngay) tại Tuyensinh247.com. Cập nhật bám sát bộ SGK mới, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.