Tìm kiếm nhị phân Python tìm vị trí của một mục trong một mảng được sắp xếp. Nó chia một nửa danh sách. Nếu một giá trị được chỉ định cao hơn số ở giữa, thì tìm kiếm sẽ tập trung vào bên phải danh sách. Nếu không, tìm kiếm sẽ tìm số ở bên trái danh sách.
Làm thế nào để bạn tìm thấy vị trí của một mục trong danh sách? Tìm kiếm nhị phân có sự hỗ trợ của bạn. Bằng cách sử dụng tìm kiếm nhị phân, bạn có thể dễ dàng tìm thấy vị trí của một phần tử bên trong một mảng được sắp xếp.
Máy tính rất tốt trong việc tìm kiếm thông qua các danh sách để tìm một mục cụ thể. Các quy tắc mà máy tính sử dụng để tìm các mục trong danh sách được gọi là thuật toán tìm kiếm. Một trong những thuật toán Python phổ biến nhất là tìm kiếm nhị phân.
Trong hướng dẫn này, chúng ta sẽ thảo luận về tìm kiếm nhị phân là gì và cách chúng hoạt động. Chúng tôi sẽ giới thiệu cho các bạn một ví dụ về tìm kiếm nhị phân trong Python để bạn có thể tìm hiểu cách viết một tìm kiếm vào chương trình của mình. Hãy bắt đầu!
Tìm kiếm nhị phân trong Python là gì?
Tìm kiếm nhị phân Python là một thuật toán tìm vị trí của một phần tử trong một mảng có thứ tự. Các tìm kiếm nhị phân lặp đi lặp lại chia một danh sách thành hai nửa. Sau đó, tìm kiếm sẽ so sánh xem một giá trị cao hơn hay thấp hơn giá trị giữa trong danh sách.
Có hai cách bạn có thể thực hiện tìm kiếm nhị phân. Cả hai phương pháp đều đặt các con trỏ được sử dụng để theo dõi các vị trí cao nhất và thấp nhất tại một điểm cụ thể trong một mảng.
Cách tiếp cận đầu tiên bạn có thể sử dụng là phương pháp lặp lại. Trong cách tiếp cận này, một tập hợp các câu lệnh được lặp lại để xác định vị trí của một phần tử trong một mảng. Trong Python, chúng tôi sử dụng một while vòng lặp cho mục đích này.
Cách tiếp cận khác là phương pháp đệ quy. Đây là nơi bạn viết một hàm gọi đi gọi lại chính nó cho đến khi tìm thấy một phần tử trong danh sách. Phương pháp đệ quy sử dụng phương pháp chia và chinh phục mà chúng ta đã thảo luận trước đó và lặp lại quá trình tìm kiếm cho đến khi tìm thấy một phần tử.
81% người tham gia cho biết họ cảm thấy tự tin hơn về triển vọng công việc công nghệ của mình sau khi tham gia một cuộc thi đào tạo. Kết hợp với bootcamp ngay hôm nay.
Sinh viên tốt nghiệp bootcamp trung bình đã dành ít hơn sáu tháng để chuyển đổi nghề nghiệp, từ khi bắt đầu bootcamp đến khi tìm được công việc đầu tiên của họ.
Python cây tìm kiếm nhị phân:Từng bước
Với tất cả những gì nói về chia và chinh phục và đệ quy, có thể dễ dàng mất dấu cách hoạt động của một tìm kiếm nhị phân chính xác. Vì lý do đó, chúng ta sẽ đi thẳng vào một ví dụ về cách hoạt động của tìm kiếm nhị phân. Xem xét danh sách sau:
| 7 | 9 | 14 | 22 | 34 |
Chúng tôi sẽ tìm kiếm số “22” trong danh sách của chúng tôi.
Để bắt đầu, chúng tôi sẽ thiết lập hai con trỏ trong danh sách của chúng tôi. Một con trỏ sẽ phản ánh giá trị cao nhất trong danh sách và điểm còn lại sẽ phản ánh giá trị thấp nhất:
| Thấp | | | | Cao |
| 7 | 9 | 14 | 22 | 34 |
Bước tiếp theo của chúng ta là tìm phần tử ở giữa trong mảng, là 14. Nếu giá trị này bằng với giá trị mà chúng ta đang tìm kiếm, thì giá trị này sẽ được trả về.
Trong trường hợp này, 14 không giống với 22. Vì vậy, chương trình của chúng ta cần thực hiện một phép so sánh.
Chúng ta sẽ so sánh số mà chúng ta đang tìm kiếm với phần tử ở giữa của các phần tử ở phía bên phải của phần tử ở giữa hiện tại. Chúng tôi sẽ chỉ làm điều này nếu số mà chúng tôi đang tìm kiếm lớn hơn số ở giữa. Nếu không, chúng tôi sẽ so sánh phần tử với phần tử giữa ở bên trái của phần tử giữa hiện tại.
Số 22 lớn hơn 14. Chương trình của chúng tôi bắt đầu so sánh số 22 với phần tử giữa ở phía bên phải của phần tử giữa hiện tại của chúng tôi (14). Trong trường hợp này, con số đó là 22. Con số này bằng với số chúng tôi đang tìm kiếm.
| | | Thấp | Trung | Cao |
| 7 | 9 | 14 | 22 | 34 |
Chúng tôi đã tìm thấy giá trị trung bình của mình. Chương trình của chúng tôi bây giờ sẽ trả về vị trí chỉ mục của số đó. Trong trường hợp này, vị trí chỉ mục của 22 là 3 (hãy nhớ rằng danh sách được lập chỉ mục bắt đầu từ 0!).
Cách triển khai tìm kiếm nhị phân trong Python
Hãy bắt tay vào làm bẩn với một số mã Python. Chúng ta sẽ khám phá cách triển khai tìm kiếm nhị phân trong Python bằng cả hai cách tiếp cận mà chúng ta đã thảo luận trước đó:phương pháp lặp lại và phương thức đệ quy.
Tìm kiếm nhị phân lặp lại trong Python
Chúng ta sẽ bắt đầu với phương pháp lặp lại. Đây là nơi chúng tôi sẽ lặp lại mọi mục trong danh sách của mình. Sau đó, chúng tôi sẽ tìm giá trị giữa trong danh sách. Chúng tôi sẽ tiếp tục làm như vậy cho đến khi chúng tôi tìm thấy giá trị mà chúng tôi đang tìm kiếm.
Hàm tìm kiếm nhị phân
Hãy bắt đầu bằng cách xác định một hàm Python cho tìm kiếm nhị phân của chúng tôi:
def findValue(numbers, number_to_find): low = 0 high = len(listnumbers - 1 while low <= high: middle = low + (high - low) // 2 if numbers[middle] == number_to_find: return middle elif numbers[middle] < number_to_find: low = middle + 1 else: high = middle - 1 return -1
Hàm của chúng ta chấp nhận hai tham số:danh sách mà chúng ta muốn tìm kiếm và số mà chúng ta muốn tìm trong danh sách của mình.
Sau đó, chúng tôi đã khai báo hai biến Python lưu trữ các giá trị mặc định cho các giá trị thấp nhất và cao nhất trong danh sách. thấp được đặt thành 0, là giá trị chỉ mục bắt đầu trong danh sách. cao được đặt thành độ dài của danh sách trừ đi một (vì danh sách được lập chỉ mục từ 0).
Bước tiếp theo của chúng tôi là khai báo một vòng lặp while trong Python. Vòng lặp này chạy trong khi phần tử thấp nhất nhỏ hơn hoặc bằng số cao nhất. Điều này có nghĩa là vòng lặp của chúng tôi sẽ chỉ chạy nếu số của chúng tôi vẫn chưa được tìm thấy.
Sau đó, chúng tôi tính số giữa. Chúng tôi thực hiện điều này bằng cách lấy giá trị cao nhất trừ đi giá trị thấp nhất. Sau đó, chúng tôi tính mô-đun (phần dư) của số đó khi chia cho 2. Sau đó, chúng tôi cộng mô-đun vào giá trị của số thấp nhất.
Nếu số ở giữa trong danh sách của chúng tôi giống với số chúng tôi muốn tìm, chúng tôi trả về vị trí của số đó.
Chúng tôi đặt số "thấp" mới của mình bằng một lớn hơn vị trí ở giữa. Điều này xảy ra nếu số ở giữa nhỏ hơn số mà chúng ta muốn tìm. Điều này di chuyển tìm kiếm của chúng tôi xuống phía bên trái của danh sách, giống như chúng tôi đã làm trong ví dụ trực quan trước đó.
Nếu không, chúng tôi đặt số "cao" của chúng tôi bằng một ít hơn vị trí giữa. Điều này di chuyển tìm kiếm của chúng tôi sang phía bên phải danh sách của chúng tôi.
Điều này được lặp lại cho đến khi mức thấp bằng hoặc nhỏ hơn mức cao. Nếu giá trị của chúng tôi không được tìm thấy, chúng tôi trả về -1. Chúng ta sẽ nói về lý do trong một phút nữa.
Thực hiện tìm kiếm
Thêm mã sau vào cuối chương trình của bạn, bên ngoài findValue chức năng:
numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find)
if final == -1:
print("This item was not found in the list.")
else:
print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")
Chúng tôi đã bắt đầu bằng cách khai báo danh sách các mục mà chúng tôi muốn tìm kiếm. Sau đó, chúng tôi đã chỉ định số chúng tôi muốn tìm, là 22.
Tiếp theo, chúng tôi gọi findValue () của chúng tôi chức năng và chuyển qua nó trong danh sách.
Đây là nơi -1 đến từ trước đó. Nếu số được trả về bởi hàm của chúng tôi là -1, điều đó có nghĩa là mục của chúng tôi không được tìm thấy trong danh sách. Các lập trình viên thường sử dụng -1 trong những trường hợp như thế này vì hàm tìm kiếm của chúng tôi không thể trả về số âm.
Nếu không, chương trình của chúng tôi sẽ in ra một thông báo cho chúng tôi biết vị trí chỉ mục của giá trị đó.
Mã của chúng tôi trả về:
The number 22 was found at index position 3.
Bây giờ chúng ta biết rằng số 22 xuất hiện ở vị trí chỉ mục 3.
Tìm kiếm nhị phân đệ quy trong Python
Chúng ta cũng có thể sử dụng đệ quy để thực hiện tìm kiếm nhị phân. Đây là nơi chúng tôi sẽ xác định một hàm tiếp tục gọi chính nó cho đến khi một điều kiện - số của chúng tôi đang được tìm thấy - được đáp ứng.
Xác định một hàm đệ quy
Giống như trong ví dụ cuối cùng của chúng tôi, chúng tôi sẽ bắt đầu bằng cách viết một hàm thực hiện tìm kiếm nhị phân của chúng tôi:
def findValue(numbers, number_to_find, low, high): if high >= low: middle = low + (high - low) // 2 if numbers[middle] == number_to_find: return middle elif numbers[middle] < number_to_find: return findValue(numbers, number_to_find, middle + 1, high) else: return findValue(numbers, number_to_find, low, middle - 1) else: return -1
Mã của chúng tôi hơi giống với ví dụ cuối cùng của chúng tôi.
Chúng tôi bắt đầu bằng cách kiểm tra xem giá trị cao nhất lớn hơn hoặc bằng giá trị thấp. Nếu đúng như vậy, chương trình của chúng ta sẽ trả về -1. Nếu không, nó sẽ bắt đầu thực hiện tìm kiếm nhị phân.
Chúng tôi tính toán số ở giữa bằng cách sử dụng cách tiếp cận tương tự như trong ví dụ cuối cùng. Đầu tiên, chúng tôi lấy giá trị cao nhất trừ giá trị thấp nhất. Sau đó, chúng tôi tính mô-đun (phần dư) của giá trị đó khi chia cho 2. Cuối cùng, chúng tôi cộng số thấp nhất.
Sau đó, chúng tôi đã viết một nếu tuyên bố quyết định cách tìm kiếm nhị phân của chúng tôi sẽ tiến hành:
- Nếu số ở giữa bằng với số chúng ta đang tìm, thì vị trí của số đó sẽ được trả về.
- Nếu số ở giữa nhỏ hơn số chúng tôi đang tìm kiếm, thì findValue () của chúng tôi hàm được gọi lại. Lần này, giá trị của thấp được đặt bằng một giá trị lớn hơn giá trị trung bình của chúng tôi.
- Nếu số ở giữa lớn hơn số mà chúng tôi đang tìm kiếm, thì findValue () hàm được gọi. Giá trị của "cao" sẽ bằng một nhỏ hơn giá trị trung bình.
Viết chương trình chính
Tất cả những gì chúng tôi còn lại phải làm là viết chương trình chính của chúng tôi:
numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find, 0, len(numbers) - 1)
if final == -1:
print("This item was not found in the list.")
else:
print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")
Chương trình chính của chúng tôi cũng giống như chương trình ví dụ trước đó của chúng tôi, một điểm khác biệt. Chúng tôi đang chuyển hai tham số mới vào findValue () của chúng tôi chức năng:thấp và cao.
Chúng tôi cần làm điều này vì thuật toán của chúng tôi là đệ quy và chúng tôi không thể chỉ định các giá trị đó trong hàm của mình. Nếu chúng tôi chỉ định các giá trị trong hàm của mình, các giá trị đó sẽ được đặt lại mỗi khi hàm của chúng tôi được thực thi, điều này sẽ phá vỡ thuật toán tìm kiếm của chúng tôi.
Mã của chúng tôi trả về:
The number 22 was found at index position 3.
Chúng tôi đã nhận được kết quả tương tự từ trước đó. Trong ví dụ này, chúng tôi đã sử dụng chương trình đệ quy thay vì chương trình lặp lại để thực hiện tìm kiếm nhị phân của mình.
Khi nào bạn nên sử dụng tìm kiếm nhị phân trong Python?
Tìm kiếm nhị phân là một cách hiệu quả để tìm kiếm thông qua danh sách các số. Tìm kiếm này hiệu quả hơn tìm kiếm tuyến tính. Điều này là do phương pháp nhị phân cắt giảm lượng tìm kiếm của bạn xuống một nửa ngay khi bạn tìm thấy phần giữa của danh sách được sắp xếp.
Điều quan trọng cần lưu ý là danh sách phải được sắp xếp theo số trước khi có thể tìm kiếm bằng tìm kiếm nhị phân. Trước khi bạn thực hiện tìm kiếm nhị phân, hãy đảm bảo rằng các số của bạn được sắp xếp theo thứ tự tăng dần.
Tìm kiếm nhị phân trong Phân tích độ phức tạp của Python
Độ phức tạp của tìm kiếm nhị phân là gì? Đó là một câu hỏi hay.
Thuật toán tìm kiếm nhị phân có độ phức tạp trường hợp tốt nhất là O (1). Điều này xảy ra khi so sánh đầu tiên bằng với mục mà bạn đang tìm kiếm.
Độ phức tạp trung bình và trường hợp xấu nhất cho một tìm kiếm nhị phân là O (log n). Điều này có nghĩa là khoảng thời gian cần thiết để thực hiện tìm kiếm tăng theo lôgarit tùy thuộc vào số lượng mục cần tìm kiếm trong danh sách.
Kết luận
Tìm kiếm nhị phân là một cách hiệu quả để tìm vị trí chỉ mục của một giá trị trong danh sách.
Mỗi khi chạy tìm kiếm nhị phân, tìm kiếm sẽ chia danh sách thành hai phần. Tìm kiếm tập trung vào phía bên của danh sách gần nhất với số mà bạn đang tìm kiếm.
Đối với mỗi lần tìm kiếm được chạy, lượng số mà chương trình cần tìm kiếm sẽ giảm đi một nửa.
Để tìm hiểu thêm về Python, hãy đọc hướng dẫn Cách học Python của chúng tôi.