Nhờ mọi người giải thích code tìm kiếm nhị phân để tìm phần tử trong list đã được sắp xếp

Em chào mọi người, em đang học 1 bài có đề bài như sau:

Và code mẫu là:

import math
def bin_search(li, element):
 bottom = 0
 top = len(li)-1
 index = -1
 while top>=bottom and index==-1:
   mid = int(math.floor((top+bottom)/2.0))
   if li[mid]==element:
     index = mid
   elif li[mid]>element:
     top = mid-1
   else:
     bottom = mid+1
 return index

li=[2,5,7,9,11,17,222]
print (bin_search(li,11))
print (bin_search(li,12))

Chỗ em không hiểu là vì sao top=len(li)-1index = -1 ạ? element có phải = 7 hay không? Và tại sao 2 dòng lệnh print() ở cuối lại có 11 với 12 ạ? Em xin cảm ơn.

  • Chỉ số mảng là từ 0 -> len() - 1.
  • index = -1 là khởi tạo ban đầu cho trường hợp không tìm thấy giá trị trong list, sẽ trả về -1.

Đó là 2 giá trị cần tìm.

4 Likes

Chia nguyên là // nhé bạn :slight_smile:

4 Likes

vậy bạn có thể làm rõ dùm mình đoạn code này không:

if li[mid]==element và elif li[mid]>element:

mình không rõ element có giá trị gì ạ, có phải nó nói về số phần tử trong list li không

Element là phần tử bạn đang tìm kiếm, có trị khi bạn nạp vào hàm còn gì. Đoạn:

if li[mid]==element và elif li[mid]>element:
nghĩa là nếu phần tử element cần tìm bằng giá trị số ở giữa thì vị trí giữa chính là phần tử, xuất ra vị trí index
nếu không elif phần tử cần tìm lớn hơn giá trị số ở giữa thì…

Để tránh rối, ta thử giải thuật trên trong thực tế qua trò chơi như sau:
Bạn: tao đoán một con số nhỏ hơn 10 (top) và lớn hơn -1 (zero, tức bottom), đố mày là số nào.
Tui: số đó lớn hơn 5 hay nhỏ hơn 5 (mid)
Bạn: lớn hơn 5
Tui: số đó lớn hơn 7 hay nhỏ hơn 7 (mid tiếp)
Bạn: nhỏ hơn 7
Tui: đó là số 6 (element = số bạn đoán = số cần tìm)
Bạn tự kiếm thêm các yếu tố khác từ trò chơi vào bài giải thuật của bạn để hiểu.

3 Likes

mình thấy lời hướng dẫn của bạn rất tâm huyết. Mình cảm ơn bạn rất nhiều :heart_eyes::heart_eyes::heart_eyes:

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?