Câu hỏi:

13/07/2024 942

Với thuật toán tìm kiếm nhị phân, cần duyệt bao nhiêu phần tử để tìm ra phân tử có giá trị bằng 34?

Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).

Tổng ôn toán Tổng ôn lý Các môn khác

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Với dãy A = {0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67}, và sử dụng thuật toán tìm kiếm nhị phân, số lần duyệt cần thực hiện để tìm ra phần tử có giá trị bằng 34 là 2 lần.

Quy trình tìm kiếm nhị phân hoạt động bằng cách so sánh giá trị cần tìm với giá trị ở giữa dãy, và dựa vào kết quả của so sánh này để tiếp tục tìm kiếm trong nửa đầu dãy chứa giá trị cần tìm. Lần đầu tiên duyệt, ta so sánh giá trị cần tìm (34) với giá trị ở giữa dãy, tại vị trí (0 + 11)/2 = 5. Vì giá trị tại vị trí này là 14 và 34 > 14, nên ta sẽ tiếp tục tìm kiếm trong nửa đầu dãy phải của vị trí này. Lần duyệt tiếp theo, ta so sánh giá trị cần tìm với giá trị ở giữa dãy, tại vị trí (5 + 11)/2 = 8. Vì giá trị tại vị trí này là 31 và 34 > 31, nên ta sẽ tiếp tục tìm kiếm trong nửa đầu dãy phải của vị trí này. Lần duyệt tiếp theo, giá trị cần tìm là 34 và giá trị tại vị trí này cũng là 34, nên ta đã tìm thấy phần tử cần tìm.

Tổng cộng, số lần duyệt cần thực hiện là 2 lần để tìm ra phần tử có giá trị bằng 34 bằng thuật toán tìm kiếm nhị phân trong dãy A này.

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

Cho dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu lần duyệt để tìm ra phần tử có giá trị bằng 47 trong dãy?

Xem đáp án » 13/07/2024 2,778

Câu 2:

Cho dãy A= {0, 4, 9, 10, 12,14, 17, 18, 20, 31, 34, 67}

Với thuật toán tìm kiếm tuần tự, cần duyệt bao nhiêu phần tử để tìm ra phần từ có giá trị bằng 34?

Xem đáp án » 11/07/2024 2,197

Câu 3:

Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ.

Xem đáp án » 13/07/2024 1,487

Câu 4:

Thay vị lần lượt lật các thẻ từ đầu đến cuối, bạn Minh đã chơi như sau: Đầu Tiên Minh lật thẻ ở giữa, sau đó tuỳ theo số ghi trên thẻ là lớn hơn hay nhỏ hơn số K mà lạt tiếp thẻ ở ngay bên trái hoặc ngay bên phải thẻ ở giữa. Trong trường hợp này, số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là bao nhiêu?

Xem đáp án » 13/07/2024 973

Câu 5:

Cho A là danh sách tên các học sinh trong lớp được sắp xếp theo thứ tự bảng chữ cái, viết thương trình tìm kiếm nhị phân để tìm ra các học sinh có tên là Minh.

Xem đáp án » 11/07/2024 898

Câu 6:

Em hãy chỉnh sửa thuật toán tìm tuần tự để tìm ra tất cả các phần tử trong dãy bằng giá trị cần tìm, biết dãy đó có nhiều phân tử bằng giá trị cần tìm.

Xem đáp án » 13/07/2024 585

Bình luận


Bình luận
Đăng ký gói thi VIP

VIP 1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 2 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 3 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 4 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Siêu tiết kiệm - Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

Sách cho 2k7 ôn luyện THPT-vs-DGNL