Hướng dẫn binary search string python
Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là Binary Search, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Binary Search thông qua các phần sau. Show
Cho một mảng đã sắp xếp arr [] gồm n phần tử, hãy viết một hàm để tìm kiếm một phần tử x đã cho trong arr []. Một cách tiếp cận đơn giản là thực hiện tìm kiếm tuyến tính(Linear Search), độ phức tạp thời gian của thuật toán trên là O (n). Một cách tiếp cận khác để thực hiện tác vụ tương tự là sử dụng Tìm kiếm nhị phân. Tìm kiếm nhị phân(Binary Search): Tìm kiếm một mảng được sắp xếp bằng cách chia đôi khoảng thời gian tìm kiếm nhiều lần. Bắt đầu với một khoảng bao gồm toàn bộ mảng. Nếu giá trị của key tìm kiếm nhỏ hơn mục ở khoảng giữa, hãy thu hẹp khoảng đó xuống nửa dưới. Nếu không, hãy thu hẹp nó ở nửa trên. Lặp lại kiểm tra cho đến khi giá trị được tìm thấy hoặc khoảng thời gian trống. Ý tưởng của tìm kiếm nhị phân là sử dụng thông tin mà mảng được sắp xếp và giảm độ phức tạp về thời gian thành O (Log n). Về cơ bản chúng ta bỏ qua một nửa số phần tử chỉ sau một lần so sánh.
2. Code ví dụ trên nhiều ngôn ngữ2.1 Triển khai đệ quy với Tìm kiếm nhị phân(Binary Search)C++
C
Java
Python 3
C#
PHP
Kết quả:
2.2 Thực hiện lặp đi lặp lại để Tìm kiếm nhị phân(Binary Search)C++
C
Java
Python 3
C#
PHP
Kết quả:
3. Độ phức tạpThời gian phức tạp: Độ phức tạp về thời gian của Tìm kiếm nhị phân có thể được viết là T(n) = T(n/2) + c Sự lặp lại ở trên có thể được giải quyết bằng
cách sử dụng phương pháp đệ quy tree hoặc phương pháp Master. Nó nằm trong trường hợp II của Phương pháp Master và giải pháp của sự tái diễn là Không gian phụ trợ: O (1) trong trường hợp thực hiện lặp đi lặp lại. Trong trường hợp thực hiện đệ quy, không gian ngăn xếp gọi đệ quy O (Logn). Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng! Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you! |