Thời gian tới tệ nhất cho tìm kiếm nhị phân một phần tử trong một mảng là gì

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

Nội dung chính Show

Thời gian phức tạp
Độ phức tạp của không gian
10 bước để thành thạo Python cho khoa học dữ liệu
Quy trình 10 bước để trở thành bậc thầy về Python cho Khoa học dữ liệu và Học máy
10 ứng dụng tuyệt vời trong thế giới thực của khoa học dữ liệu và AI
Hiểu và phân tích việc sử dụng AI và Khoa học dữ liệu hàng ngày trong thế giới thực
Làm chủ danh sách Python để lập trình
Hiểu chi tiết về tất cả các khái niệm về danh sách Cần thiết cho Lập trình. Tại sao nên sử dụng danh sách cho Khoa học dữ liệu và…
IoT và trí tuệ nhân tạo. Một sự tiến hóa mạnh mẽ cho các thế hệ tương lai
Internet vạn vật kết hợp với trí tuệ nhân tạo sẽ là bước tiến hóa trong tương lai của nhân loại. Đây là…
3 cách để tận dụng sức mạnh của trí tuệ nhân tạo cho hoạt động tiếp thị của bạn ngay hôm nay
3 lý do bạn nên xem xét trí tuệ nhân tạo cho mục đích tiếp thị của mình với một số liên kết hữu ích để giúp bạn…
Tìm kiếm nhị phân có nghĩa là gì?
Tìm kiếm nhị phân với các ví dụ là gì?
Tìm kiếm nhị phân trong Python w3schools là gì?

Trong toán học và khoa học máy tính, thuật toán là một chuỗi hữu hạn các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính, thường để giải một loại bài toán hoặc để thực hiện một phép tính. Một thuật toán như vậy mà chúng tôi sẽ trình bày trong bài viết này là thuật toán tìm kiếm nhị phân

Trong khoa học máy tính, tìm kiếm nhị phân, còn được gọi là tìm kiếm nửa khoảng, tìm kiếm logarit hoặc cắt nhị phân, là một thuật toán tìm kiếm tìm vị trí của một giá trị đích trong một mảng được sắp xếp. 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 mà mục tiêu không thể nói dối sẽ bị loại bỏ và quá trình tìm kiếm tiếp tục trên nửa còn 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 và lặp lại điều này cho đến khi tìm thấy giá trị mục tiêu. Nếu tìm kiếm kết thúc với nửa còn lại trống, mục tiêu không có trong mảng

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

Sau đó, chúng ta sẽ hiểu trực giác từng bước của việc thực hiện thuật toán tìm kiếm nhị phân. Sau đó, chúng tôi sẽ tiến hành làm bẩn tay với một số mã và cuối cùng, chúng tôi sẽ hiểu các biện 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 máy tính, tìm kiếm tuyến tính hoặc tìm kiếm tuần tự là một phương pháp tìm kiếm một phần tử trong danh sách. Nó tuần tự kiểm tra từng phần tử của danh sách cho đến khi tìm thấy kết quả phù hợp hoặc toàn bộ danh sách đã được tìm kiếm

Trong tìm kiếm tuyến tính, bạn lặp qua tất cả các phần tử trong danh sách theo cách đơn giản cho đến khi bạn gặp giá trị mong muốn mà bạn đang tìm kiếm. Việc triển khai mã cho tìm kiếm tuyến tính khá đơn giản và sẽ được thảo luận trong phần sau của bài viết này

Một tìm kiếm tuyến tính chạy ở thời điểm tuyến tính tồi tệ nhất và thực hiện nhiều nhất n phép so sánh, trong đó n là độ dài của danh sách. 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ó trường hợp so sánh trung bình là n+1/2. Nhưng trường hợp trung bình có thể bị ảnh hưởng nếu xác suất tìm kiếm cho từng phần tử khác nhau

Tìm kiếm tuyến tính hiếm khi thực tế vì các lược đồ và thuật toán tìm kiếm khác, chẳng hạn như thuật toán tìm kiếm nhị phân và bảng băm, cho phép tìm kiếm nhanh hơn đáng kể đối với tất cả trừ các danh sách ngắn hơn

Biểu diễn đồ họa bên dưới cho thấy lý do tại sao tìm kiếm tuyến tính không được triển khai trong các tình huống thực tế và thay vào đó, một phương pháp như thuật toán tìm kiếm nhị phân được sử dụng

Hình ảnh của tác giả

Biểu đồ cho thấy khi số lượng phần tử trong danh sách hoặc mảng tăng lên, số lượng phép so sánh cũng tăng theo tuyến tính đối với thuật toán tìm kiếm tuyến tính. Do đó, đối với các vấn đề thực tế, tìm kiếm tuyến tính không bao giờ được khuyến nghị và một phương pháp 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 và cuối cùng là phân tích các biện pháp hiệu suất của nó

Trực giác từng bước 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 sách các mục đã được sắp xếp. Nó hoạt động bằng cách chia liên tục một nửa phần danh sách có thể chứa mục cho đến khi bạn thu hẹp các vị trí có thể xuống chỉ còn một vị trí. Hãy để chúng tôi hiểu việc thực hiện từng bước của thuật toán này

Sắp xếp danh sách hoặc mảng bạn có theo thứ tự tăng dần
Phần tử bắt đầu được gọi là 'L' và phần tử cuối cùng được gọi là 'R'. Sử dụng các giá trị này, chúng tôi cố gắng thu hẹp phần tử ở giữa bằng cách sử dụng công thức (L+R)//2. Hoạt động này về cơ bản thực hiện chức năng sàn để đạt được phần tử ở giữa mong muốn. Một cách tiếp cận khác là sử dụng hàm trần, nhưng chúng tôi sẽ đề cập đến phương pháp này trong bài viết hôm nay
Bước tiếp theo là kiểm tra xem giá trị của phần tử ở giữa có tương đương với giá trị mong muốn không. Nếu có, thì quá trình tìm kiếm thành công và có thể kết thúc
Nếu giá trị mong muốn nhỏ hơn phần tử ở giữa, thì tất cả các giá trị từ phần tử ở giữa đến giá trị 'R' đều bị loại bỏ. Và sự lặp lại của bước 2 và 3 diễn ra
Nếu giá trị mong muốn lớn hơn phần tử ở giữa, thì tất cả các giá trị từ phần tử ở giữa đến giá trị 'L' đều bị loại bỏ. Và sự lặp lại của bước 2 và 3 diễn ra

Chúng ta hãy xem xét một ví dụ để có được trực giác tốt hơn về hoạt động của các bước sau được đề cập ở trên. Sơ đồ dưới đây là một biểu diễn của một mảng được sắp xếp với 17 phần tử. Chúng tôi đang cố gắng xác định vị trí của mục 7. Hãy phân tích quy trình từng bước về cách thức thực hiện nhiệm vụ này

Hình ảnh từ wiki

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

Phần tử ở vị trí thứ 8 là 14, nhưng giá trị mong muốn là 7. Do đó có thể loại bỏ tất cả các phần tử từ vị trí thứ 8 đến vị trí cuối cùng. Và bước 2 và bước 3 có thể được lặp lại lần nữa. (0+7)//2 sẽ trả về vị trí là 3 và giá trị là 6. Giá trị mong muốn lớn hơn giá trị tìm thấy. Do đó, chúng ta có thể làm theo bước thứ năm và lặp lại bước 2 và 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 xem nên xem phần giải thích sau đây từ wiki

Mã số

Trong phần này, chúng ta hãy bắt tay vào viết mã. Chúng ta sẽ bắt đầ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á đơn giản và 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

Thuật toán tìm kiếm tuyến tính rất đơn giản để thực hiện, như được hiển thị trong đoạn mã trên. Bạn lặp qua toàn bộ mảng cho đến khi bạn tìm thấy vị trí của phần tử mà bạn đang tìm kiếm. Khi bạn đã tìm thấy số thành công, bạn có thể in ra vị trí tìm thấy vật phẩm. Đầu ra “bốn” cho thấy rằng phần tử mong muốn đã được tìm thấy ở vị trí thứ tư của mảng hoặc danh sách

Tiếp theo, chúng ta sẽ xem xét việc triển khai thuật toán tìm kiếm nhị phân. Có nhiều phương pháp thực hiện thuật toán này, như cách lặp hoặc đệ quy. Trong bài viết này, chúng tôi sẽ tập trung vào một phương pháp đơn giản để thực hiện nhiệm vụ này

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

Output: 4

Việc triển khai thuật toán tìm kiếm nhị phân trong khối mã trên chính xác như đã giải thích trong phần trước của bài viết. Mã này là một đại diện của việc thực hiện từng bước chính xác của quy trình tìm kiếm nhị phân. Đầu ra “bốn” cho thấy rằng phần tử mong muốn đã được tìm thấy ở vị trí thứ tư của mảng hoặc danh sách

Tôi thực sự khuyên bạn nên xem một số bài viết trong phần tham khảo ở cuối bài viết này để hiểu rõ hơn về cách triển khai cũng như có thêm kiến thức về mã hóa của từng phương pháp của thuật toán tìm kiếm nhị phân

Màn biểu diễn

Xét về số lần so sánh, hiệu suất của tìm kiếm nhị phân có thể được phân tích bằng cách xem quy trình chạy trên cây nhị phân. Sơ đồ dưới đây là một đạ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 và 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 còn lại của cây được xây dựng theo cách tương tự. Bắt đầu từ nút gốc, các cây con bên trái hoặc bên phải được duyệt tùy thuộc vào việc giá trị mục tiêu nhỏ hơn hay nhiều hơn nút đang xem xét

Thời gian phức tạp

Kịch bản trường hợp tốt nhất = O(1)

Kịch bản trường hợp trung bình = O(log n)

Kịch bản trường hợp xấu nhất = O(log n)

Tìm kiếm nhị phân chạy trong thời gian logarit trong trường hợp xấu nhất, so sánh O(log n), trong đó n là số phần tử trong mảng. Tìm kiếm nhị phân nhanh hơn tìm kiếm tuyến tính ngoại trừ các mảng nhỏ. Tuy nhiên, mảng phải được sắp xếp trước để có thể áp dụng tìm kiếm nhị phân

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

Độ phức tạp của không gian

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

Mặc dù ý tưởng cơ bản của tìm kiếm nhị phân tương đối đơn giản, nhưng các chi tiết có thể phức tạp một cách đáng ngạc nhiên
— Donald Knuth

Trong thời hiện đại, thuật toán tìm kiếm nhị phân có một chức năng riêng trong hầu hết mọi ngôn ngữ lập trình chính và có thể được thực hiện dễ dàng bằng cách sử dụng các chức năng đó. Python cung cấp mô-đun bisect để thực hiện thuật toán tìm kiếm nhị phân dễ dàng hơn

Sự kết luận

Ảnh của Christopher Gower trên Bapt

Trong bài viết này, chúng tôi đã thảo luậ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ơ bản trong khoa học máy tính. Nó có thể tìm thấy chỉ mục của một phần tử trong danh sách được sắp xếp một cách hiệu quả bằng cách lặp đi lặp lại một nửa phạm vi tìm kiếm cho đến khi phần tử được tìm thấy, vì vậy thời gian chạy của nó là logarit của kích thước danh sách

Chúng tôi cũng đã làm bẩn tay với một số mã python bổ sung và hiểu sơ qua về cách thức hoạt động của nó trong một kịch bản trong danh sách các phần tử được sắp xếp. Sau khi triển khai nó trong Python, chúng tôi đã đề cập đến một số chủ đề thiết yếu khác liên quan đến hiệu suất của nó, chẳng hạn như độ phức tạp của không gian và thời gian, đây là thước đo hữu ích trong lĩnh vực khoa học máy tính để xác thực hoạt động của các mô hình

Nếu bạn có bất kỳ câu hỏi nào liên quan đến nội dung trong bài viết này, vui lòng liên hệ với tôi bên dưới và tôi sẽ đảm bảo trả lời bạn sớm nhất có thể. Nếu bạn 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ư vậy

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