Hiểu thuật toán tìm kiếm nhị phân trong Python

Hiểu biết cụ thể về hoạt động của thuật toán tìm kiếm nhị phân & việc triển khai nó trong python

Ảnh của David Nicolai trên Unsplash

Thuật toán là một góc cạnh cần thiết của lập trình. Trong nội dung này, chúng tôi sẽ đề cập đến một thuật toán thú vị như thế có thể được sử dụng để tìm địa điểm của một phần tử rõ ràng trong danh mục hoặc mảng một cách hiệu quả. Chúng tôi sẽ trình bày đầy đủ cụ thể về thuật toán tìm kiếm nhị phân & phấn đấu triển khai nó với python.

Trong toán học & khoa học laptop, thuật toán là một chuỗi hữu hạn các chỉ dẫn được xác nhận rõ ràng và cụ thể, có thể thực hiện được thuộc máy tính, thường để khắc phục một lớp vấn đề hoặc để thực hiện một phép tính. Một trong những thuật toán mà chúng tôi sẽ đề cập trong nội dung đó là thuật toán tìm kiếm nhị phân.

Trong khoa học laptop, tìm kiếm nhị phân, còn gọi là tìm kiếm nửa khoảng, tìm kiếm theo lôgarit hoặc tìm kiếm nhị phân, là một thuật toán tìm kiếm để tìm địa điểm của giá trị đích trong một mảng được xếp đặt. Tìm kiếm nhị phân so sánh giá trị đích với phần tử giữa của mảng.

Nếu chúng không bằng nhau, nửa trong đó mục tiêu chẳng thể nói dối sẽ bị loại bỏ & tiếp tục tìm kiếm trên nửa sót lại, một lần nữa lấy phần tử ở giữa để so sánh với giá trị mục tiêu & lặp lại điều này cho đến khi tìm thấy giá trị mục tiêu. Nếu chấm dứt tìm kiếm với một nửa sót lại trống, thì mục tiêu không có trong mảng.

Trước khi đi sâu vào tìm hiểu cụ thể của thuật toán tìm kiếm nhị phân, tất cả chúng ta sẽ đề cập đến thuật toán tìm kiếm tuyến tính, điều này sẽ giúp tất cả chúng ta hiểu được tầm trọng yếu của thuật toán tìm kiếm nhị phân.

Sau đó, tất cả chúng ta sẽ hiểu trực giác từng bước của việc triển khai thuật toán tìm kiếm nhị phân. Sau đó, chúng tôi sẽ tiếp tục làm bẩn tay với một số mã, & cuối cùng, chúng tôi sẽ hiểu các phương pháp khác nhau của thuật toán tìm kiếm nhị phân.

Thuật toán tìm kiếm tuyến tính:

Trong khoa học laptop, tìm kiếm tuyến tính hoặc tìm kiếm tuần tự là một công thức để tìm một phần tử trong danh mục. Nó tuần tự kiểm soát từng phần tử của danh mục cho đến khi tìm thấy kết quả khớp hoặc toàn thể danh mục đã được tìm kiếm.

Trong tìm kiếm tuyến tính, bạn lặp qua toàn bộ các phần tử trong danh mục một cách dễ dàng cho đến khi bạn gặp giá trị mong đợi mà bạn đang tìm kiếm. Việc triển khai mã cho tìm kiếm tuyến tính khá dễ dàng & sẽ được luận bàn trong phần sau của nội dung này.

Tìm kiếm tuyến tính chạy vào thời điểm tuyến tính xấu nhất & thực hiện nhiều nhất ռ phép so sánh, trong đó ռ là độ dài của danh mục. Nếu mỗi phần tử có khả năng được tìm kiếm như nhau, thì tìm kiếm tuyến tính có một trường hợp bình quân là ռ + 1/2 so sánh. Nhưng trường hợp bình quân có thể bị tác động nếu xác suất tìm kiếm cho mỗi phần tử khác nhau.

Xem Thêm  Node.js là gì và tại sao bạn nên sử dụng nó - nút js là gì

Tìm kiếm tuyến tính ít khi thực tiễn vì các thuật toán & lược đồ tìm kiếm khác, ví dụ như thuật toán tìm kiếm nhị phân & bảng băm, cho phép tìm kiếm mau hơn đáng kể cho toàn bộ trừ các danh mục ngắn hơn.

Trình diễn đồ họa dưới đây cho thấy nguyên nhân vì sao tìm kiếm tuyến tính không được triển khai trong các tình huống thực tiễn & thay vào đó, một công thức như thuật toán tìm kiếm nhị phân được sử dụng.

Hình ảnh của Author

Biểu đồ cho thấy rằng khi số phần tử trong danh mục hoặc mảng tăng trưởng, số lượng so sánh cũng tăng tuyến tính so với thuật toán tìm kiếm tuyến tính. Vì thế, so với các vấn đề thực tiễn, tìm kiếm tuyến tính không khi nào được động viên & một công thức thay thế được gọi là thuật toán tìm kiếm nhị phân được ưu tiên hơn.

Hãy để chúng tôi hiểu trực giác từng bước của thuật toán tìm kiếm nhị phân cùng với việc triển khai nó trong python & cuối cùng là phân tích các phương pháp năng suất của nó.

Trực giác khôn ngoan của thuật toán tìm kiếm nhị phân:

Tìm kiếm nhị phân là một thuật toán hiệu quả để tìm một mục từ danh mục các mục đã được xếp đặt. Nó hoạt động bằng cách liên tục chia đôi phần danh mục có thể chứa mục cho đến khi bạn thu hẹp các địa điểm có thể chỉ còn một. Hãy để chúng tôi hiểu cách triển khai từng bước của thuật toán này.

  1. Sắp đặt danh mục hoặc mảng bạn có theo thứ tự tăng dần.
  2. Phần tử khởi đầu được gọi là ‘ɭ’ & phần tử cuối cùng được gọi là ‘Ŕ’. Sử dụng các giá trị này, chúng tôi phấn đấu thu hẹp phần tử ở giữa bằng cách thức (ɭ + Ŕ) // 2 . Hoạt động này về căn bản thực hiện một tính năng sàn để đạt được phần tử giữa mong đợi. Một cách tiếp cận thay thế là sử dụng hàm ceil, nhưng chúng tôi sẽ đề cập đến công thức này trong nội dung sau từ bây giờ.
  3. Bước kế tiếp là kiểm soát xem giá trị của phần tử ở giữa có tương tự với giá trị mong đợi hay không. Nếu có, thì tìm kiếm thành công & có thể chấm dứt.
  4. Nếu giá trị mong đợi bé hơn phần tử ở giữa, toàn bộ các giá trị từ phần tử ở giữa đến giá trị ‘Ŕ’ đều bị loại bỏ. & sự lặp lại của bước 2 & 3 diễn ra.
  5. Nếu giá trị mong đợi to hơn phần tử giữa, toàn bộ các giá trị từ phần tử giữa đến giá trị ‘ɭ’ đều bị loại bỏ. & sự lặp lại của bước 2 & 3 diễn ra.

Hình ảnh từ wiki

Sơ đồ trên chứa danh mục 17 phần tử nằm trong khoảng từ 0 đến 16. Bước trước nhất là chia danh mục bằng cách chia đôi nó thành hai nửa với cách thức nêu trên là (ɭ + Ŕ) // 2 sẽ là (16+ 0) // 2 & sẽ trả về giá trị 8.

Xem Thêm  Cách tạo trang web thân thiện với thiết bị di động: Thiết kế đáp ứng trong CSS (thesitewizard.com) - làm cho trang web đáp ứng trên thiết bị di động

Phần tử ở địa điểm thứ 8 là 14, nhưng giá trị mong đợi là 7. Vì thế có chuyên mục bỏ toàn bộ các phần tử từ địa điểm thứ 8 đến địa điểm cuối cùng. & các bước 2 & bước 3 có thể được lặp lại một lần nữa. (0 + 7) // 2 sẽ trả về địa điểm là 3 & giá trị là 6. Giá trị mong đợi to hơn giá trị tìm được. Vì thế, tất cả chúng ta có thể bắt chước bước thứ năm & lặp lại bước 2 & bước 3 một lần nữa.

Cuối cùng, giá trị của 4 có thể được tìm thấy thành công với quy trình này của thuật toán tìm kiếm nhị phân. Để hiểu điều này theo cách thuật toán hơn, tôi thực sự khuyên người đọc nên xem phần giải thích sau đây từ wiki .

Mã:

Trong phần này, tất cả chúng ta hãy làm bẩn tay với một số mã hóa. Tất cả chúng ta sẽ khởi đầu với việc triển khai thuật toán tìm kiếm tuyến tính, thuật toán này khá dễ dàng & có thể được thực hiện trong một vài dòng mã. Khối mã sau đây có thể được sử dụng để thực hiện tìm kiếm tuyến tính.

Output: 4

Kế tiếp, tất cả chúng ta sẽ suy xét việc thực hiện thuật toán tìm kiếm nhị phân. Có nhiều công thức thực hiện thuật toán này, như cách lặp lại hoặc đệ quy. Trong nội dung này, chúng tôi sẽ chăm chú vào một công thức dễ dàng để thực hiện tác vụ này.

Vấn đề tương đương được giải thích trong trực giác được khắc phục bằng thuật toán tìm kiếm nhị phân & điều này có thể được thực hiện từ khối mã được hiển thị bên dưới.

Output: 4

Tôi thực sự khuyên chúng ta nên xem một số nội dung trong phần ebook đọc qua ở cuối nội dung này để tinh thông hơn về cách triển khai cũng như có thêm kiến ​​thức về cách mã hóa từng công thức của thuật toán tìm kiếm nhị phân.

Năng suất:

Về số lượng so sánh, năng suất của tìm kiếm nhị phân có thể được phân tích bằng cách xem tiến trình chạy quy trình trên cây nhị phân. Sơ đồ dưới đây là đại diện của những điều sau đây.

Hình ảnh từ wiki

Nút gốc của cây là phần tử giữa của mảng. Phần tử giữa của nửa dưới là nút con bên trái của gốc, & phần tử giữa của nửa trên là nút con bên phải của gốc.

Phần sót lại của cây được xây dựng theo kiểu tương đương. Bắt nguồn từ nút gốc, các cây con bên trái hoặc bên phải được chuyển ngang tùy thuộc vào vào việc giá trị đích bé hơn hay nhiều hơn nút đang suy xét.

Thời gian cầu kỳ

Tình huống Trường hợp Tốt nhất = Σ (1)

Cốt chuyện trường hợp bình quân = Σ (log ռ)

Cốt chuyện trường hợp tồi tệ nhất = Σ (log ռ)

Tìm kiếm nhị phân đuổi theo thời gian logarit trong trường hợp xấu nhất, thực hiện so sánh Σ (log ռ), trong đó ռ là số phần tử trong mảng. Tìm kiếm nhị phân mau hơn tìm kiếm tuyến tính loại trừ các mảng nhỏ. Không những thế, mảng phải được xếp đặt trước để có thể ứng dụng tìm kiếm nhị phân.

Xem Thêm  Kết nối Python MongoDB - sử dụng mongodb với python

Có những kết cấu dữ liệu chuyên biệt được kiến trúc để tìm kiếm nhanh, ví dụ như bảng băm, có thể được tìm kiếm hiệu quả hơn đối với tìm kiếm nhị phân. Không những thế, tìm kiếm nhị phân có thể được sử dụng để khắc phục nhiều vấn đề hơn, ví dụ như tìm phần tử nhỏ nhất hoặc lớn nhất kế tiếp trong mảng đối với mục tiêu ngay cả khi nó không có trong mảng.

Không gian cầu kỳ

Tìm kiếm nhị phân yêu cầu ba con trỏ đến các phần tử, có thể là chỉ số mảng hoặc con trỏ đến địa điểm bộ nhớ lưu trữ, bất kì kích cỡ của mảng. Vì thế, độ cầu kỳ không gian của tìm kiếm nhị phân là Σ (1) trong mô hình tính toán Bộ nhớ đệm của Word.

Dù rằng sáng kiến căn bản của tìm kiếm nhị phân là tương đối dễ dàng, nhưng các cụ thể có thể cầu kỳ một cách đáng bất ngờ

– Donald Knuth

Trong đương đại, thuật toán tìm kiếm nhị phân có một tính năng riêng trong chủ yếu các ngôn từ lập trình chính & có thể được thực hiện đơn giản bằng cách dùng các tính năng đó. Python phân phối mô-đun bisect để thực hiện thuật toán tìm kiếm nhị phân đơn giản hơn.

Phần tổng kết:

Ảnh của Christopher Gower trên Unsplash

Trong nội dung này, chúng tôi đã luận bàn về việc triển khai thủ tục của thuật toán tìm kiếm nhị phân, một trong những thuật toán căn bản trong khoa học laptop. Nó có thể tìm chỉ mục của một phần tử trong danh mục đã xếp đặt một cách hiệu quả bằng cách liên tục giảm một nửa phạm vi tìm kiếm cho đến khi phần tử được tìm thấy, vì thế thời gian chạy của nó là logarit của kích cỡ danh mục.

Chúng tôi cũng làm bẩn tay với một số mã python bổ sung & hiểu ngắn gọn cách nó hoạt động trong một cốt chuyện trong danh mục các phần tử được xếp đặt. Sau khoảng thời gian triển khai bằng Python, chúng tôi đã đề cập đến một số đề tài cần thiết khác liên quan đến năng suất của nó, ví dụ như độ cầu kỳ về không gian & thời gian, đây là một thước đo hữu dụng trong ngành nghề khoa học laptop để công nhận hoạt động của các mô hình.

Nếu bạn có bất kỳ khúc mắc nào liên quan đến bài viết trong nội dung này, vui lòng liên hệ với tôi bên dưới, & tôi sẽ bảo đảm rằng tôi sẽ comment cho bạn trong thời gian sớm nhất. Nếu bạn mong muốn thêm bất kỳ điểm bổ sung nào của riêng bạn vào bài đăng này, thì hãy làm như thế.

Kiểm soát một số bài báo khác của tôi mà bạn có thể thích đọc!

Cảm ơn toàn bộ các bạn đã đồng hành cho đến cuối cùng. Tôi ước ao các bạn thích đọc nội dung này. Tôi chúc toàn bộ các bạn có một ngày tuyệt vời phía trước!

Người giới thiệu:

Viết một bình luận