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, tìm kiếm sẽ tập trung vào bên phải của danh sách. Mặt khác, tìm kiếm sẽ tìm số ở bên trái của 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? . 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 đã sắp xếp
Tìm trận đấu Bootcamp của bạn
- Career Karma kết hợp bạn với các bootcamp công nghệ hàng đầu
- Truy cập học bổng độc quyền và các khóa học chuẩn bị
Tên
Họ
Điện thoại .
By continuing you agree to our Terms of Service and Privacy Policy, and you consent to receive offers and opportunities from Career Karma by telephone, text message, and email.
Máy tính rất giỏi 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à chúng hoạt động như thế nào. Chúng ta sẽ xem qua 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. Bắt đầu nào
Tìm kiếm nhị phân 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ự. Tìm kiếm nhị phân liên tục chia danh sách thành hai nửa. Sau đó, tìm kiếm sẽ so sánh nếu một giá trị cao hơn hoặc 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 cách tiếp cận đều đặt con trỏ được sử dụng để theo dõi 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. 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 vòng lặp while 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 tự gọi đi gọi lại 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 để trị 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ử
Cây tìm kiếm nhị phân Python. Từng bước một
Với tất cả những gì nói về phép chia, phép chinh phục và đệ quy, có thể dễ dàng mất dấu chính xác cách thức hoạt động của tìm kiếm nhị phân. 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. Hãy xem xét danh sách sau đây
79142234Chú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 ta sẽ đặt hai con trỏ trong danh sách của mình. Một con trỏ sẽ phản ánh giá trị cao nhất trong danh sách và điểm kia sẽ phản ánh giá trị thấp nhất
Cao79142234
Bước tiếp theo của chúng tôi 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 tôi đ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 như 22. Vì vậy, chương trình của chúng ta cần thực hiện phép so sánh
» THÊM. Tìm hiểu Python cho An ninh mạng. Tài nguyên học tập, thư viện và các bước cơ bản
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 ở phí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 22 với phần tử ở giữ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. Điều này bằng với số mà chúng tôi đang tìm kiếm
ThấpTrung bìnhCao79142234
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 thực hiện tìm kiếm nhị phân trong Python
Hãy làm bẩn tay với một số mã Python. Chúng ta sẽ khám phá cách triển khai Python của tìm kiếm nhị phân bằng cách sử dụng cả hai phương pháp mà chúng ta đã thảo luận trước đó. phương pháp lặp và đệ 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 đi lặp lại. Đây là nơi chúng tôi sẽ lặp qua mọi mục trong danh sách của chúng tôi. Sau đó, chúng ta 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
Chức năng tìm kiếm nhị phân
Hãy bắt đầu bằng cách xác định 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 = 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 có lớn hơn hoặc bằng thấp không. Nếu đúng, 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 phương pháp tương tự như trong ví dụ trước. Đầu tiên, chúng tôi trừ giá trị thấp nhất từ giá trị cao nhất. Sau đó, chúng tôi tính modulo [phần dư] của giá trị đó khi chia cho 2. Cuối cùng, chúng tôi thêm số thấp nhất
Sau đó, chúng tôi đã viết một câu lệnh if quyết định cách tiến hành tìm kiếm nhị phân của chúng tôi
- Nếu số ở giữa bằng với số chúng ta đang tìm kiếm, vị trí của số đó được trả về
- Nếu số ở giữa nhỏ hơn số chúng ta đang tìm kiếm, hàm findValue[] của chúng ta sẽ được gọi lại. Lần này, giá trị 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ố chúng ta đang tìm kiếm, hàm findValue[] được gọi. Giá trị của “cao” sẽ bằng một ít hơn giá trị trung bình
» THÊM. Lỗi loại Python. đối tượng 'dict' không thể gọi được Giải pháp
Viết chương trình chính
Tất cả những gì chúng ta phải làm là viết chương trình chính của chúng ta
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 giống như ví dụ trước của chúng tôi về một điểm khác biệt. Chúng tôi đang chuyển hai tham số mới cho hàm findValue[] của chúng tôi. 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ể gán 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 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 để 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 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 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à một danh sách phải được sắp xếp theo thứ tự số trước khi có thể tìm kiếm nó 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 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ì?
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 lần 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 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 để tiến hành tìm kiếm tăng theo logarit tùy thuộc vào số lượng mục cần tìm kiếm trong danh sách
Phần 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 lần 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 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 chạy tìm kiếm, số 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
1 Xếp hạng
Về chúng tôi. Career Karma là một nền tảng được thiết kế để giúp người tìm việc tìm kiếm, nghiên cứu và kết nối với các chương trình đào tạo việc làm để thăng tiến trong sự nghiệp của họ. Tìm hiểu về ấn phẩm CK