← Level 3 · Đọc hiểu & Tình huống FE
Thuật toán & giả mã Tình huống đọc hiểu Độ khó: Nâng cao Thời gian dự kiến: Khoảng 5 phút Cấp độ phù hợp: FE Level 3 (môn B)

Truy vết thuật toán tìm kiếm nhị phân

Tìm kiếm nhị phân là thuật toán liên tục thu hẹp phạm vi tìm kiếm còn một nửa trên một mảng đã sắp xếp tăng dần để tìm giá trị mục tiêu. Đoạn giả mã dưới đây tìm target trong mảng data (tăng dần) và trả về chỉ số tìm thấy, hoặc -1 nếu không tìm thấy.

○ kiểu số nguyên: binarySearch(mảng số nguyên: data, số nguyên: target)
  số nguyên: low, high, mid
  low ← 0
  high ← (số phần tử của data) - 1
  while (low ≤ high)
    mid ← thương của (low + high) ÷ 2
    if (data[mid] bằng target) then
      return mid
    elseif (data[mid] nhỏ hơn target) then
      low ← mid + 1
    else
      high ← mid - 1
    endif
  endwhile
  return -1

Giả sử mảng data = [2, 5, 8, 12, 16, 23, 38, 45].

Từ khóa

二分探索にぶんたんさくtìm kiếm nhị phân 添字そえじchỉ số 昇順しょうじゅんthứ tự tăng dần

Câu hỏi

1

Khi target = 23, thủ tục này trả về chỉ số nào?

Lựa chọn

  1. 3
  2. 4
  3. 5
  4. 6
Xem giải thích

Lần 1: low=0, high=7, mid=3; data[3]=12<23 nên low=4. Lần 2: low=4, high=7, mid=5; data[5]=23=target nên trả về 5.

2

Ở lần lặp thứ nhất, giá trị phần tử mà mid trỏ đến là gì?

Lựa chọn

  1. 8
  2. 12
  3. 16
  4. 23
Xem giải thích

Ở lần đầu low=0, high=7, nên mid = thương của (0+7)÷2 = 3. data[3]=12.

3

Có bao nhiêu lần so sánh data[mid] với target (kiểm tra trong câu lệnh if) trước khi việc tìm target = 23 kết thúc?

Lựa chọn

  1. 1 lần
  2. 2 lần
  3. 3 lần
  4. 4 lần
Xem giải thích

Có một lần so sánh tại mid=3 (không khớp) và một lần tại mid=5 (khớp, return), tổng cộng là 2 lần.

Đăng nhập để lưu kết quả

Bạn có thể đọc miễn phí nội dung, câu hỏi và giải thích. Hãy đăng nhập để lưu kết quả và đưa vào hàng ôn tập cùng phân tích điểm yếu.

Đăng nhập để lưu