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

[baophuc2k (Tạ Bảo Phúc)]

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

Viết hàm tìm kiếm nhị phân để tìm các item trong một list đã được sắp xếp. Hàm sẽ trả lại chỉ số của phần tử được tìm thấy trong list.

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)-1 và index = -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.

[SITUVN.gcd]

Chỗ em không hiểu là vì sao top=len(li)-1 và index = -1 ạ? element có phải = 7 hay không?

• 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.

Và tại sao 2 dòng lệnh print() ở cuối lại có 11 với 12 ạ? Em xin cảm ơn.

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

[rogp10]

mid = int(math.floor((top+bottom)/2.0))

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

[baophuc2k (Tạ Bảo Phúc)]

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

[superthin (Vô Thin)]

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 đang nghĩ trong đầu 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: đó đích thị 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.

[baophuc2k (Tạ Bảo Phúc)]

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