Python chia đôi danh sách giảm dần

Trong hướng dẫn này, chúng ta sẽ tìm hiểu về thuật toán bisect, được viết bằng Python. Mã nguồn của nó được viết trong vòng 80 dòng. Chúng ta hãy đi qua phần giới thiệu về mô-đun bisect

Giới thiệu

Về cơ bản, đây là một thuật toán chia đôi để tìm điểm chèn để thêm một phần tử đã cho vào danh sách đã sắp xếp. Tuy nhiên, điều quan trọng cần nhớ là các hàm của nó lấy danh sách đã sắp xếp làm đối số. Danh sách phải được sắp xếp theo thứ tự tăng dần. Nếu danh sách đã truyền không theo thứ tự tăng dần, hàm sẽ không đưa ra lỗi, nhưng kết quả có thể không mong muốn. Bây giờ hãy hiểu các phương pháp của nó

phương pháp quan trọng

Hãy hiểu một số phương pháp thiết yếu của phương pháp bisect

  • bisect_left(a, x, lo=0, hi=None) -

Nó trả về chỉ mục i nơi phải chèn giá trị x sao cho khôi phục lại thứ tự của nó. Nếu giá trị x đã xuất hiện trong danh sách, thì chỉ mục i sẽ ở ngay trước giá trị x ngoài cùng bên trái đã có sẵn. Hãy hiểu ví dụ sau

Thí dụ -

đầu ra

The element to be inserted at place:  2

Giải trình -

Trong đoạn mã trên, chúng tôi đã xác định danh sách a và chúng tôi muốn chèn 45. Chúng tôi muốn chèn 45 để a được sắp xếp theo thứ tự. Chúng tôi đã gọi phương thức bisect_left(), phương thức này trả về 2;

Xét đoạn mã trên, chúng ta thử chèn giá trị x vào danh sách a bằng cách gọi phương thức insert() của danh sách đối tượng

Ví dụ - 2

đầu ra

[23, 40, 45, 61, 82, 100, 12, 14]

Giải trình -

Như được hiển thị trong đoạn mã trên, chúng tôi đã chèn một giá trị tại chỉ mục 3. Hãy xem một ví dụ khác nơi chúng ta sẽ sử dụng các đường chia đôi mà Mô-đun phân đôi cung cấp

Bây giờ, chúng ta sẽ chèn phần tử đã có trong danh sách

Ngoài ra, chúng tôi sẽ sử dụng các tham số lo và hi. Hãy hiểu ví dụ sau -

Ví dụ - 3

đầu ra

The element is to be insorted at: 3
[23, 40, 61, 82, 82, 100, 12, 14]

Giải trình -

Như chúng tôi đã đề cập trước đó, phương thức bisect_left tương ứng với kết quả khớp đầu tiên của giá trị x (82) trong danh sách. Các tham số lo và hi được sử dụng để chỉ định chỉ mục bắt đầu và kết thúc của danh sách mà chúng ta muốn xem xét. Nếu chúng ta không chuyển các tham số này, toàn bộ danh sách sẽ được xem xét, như đã thấy trong ví dụ trước. Hãy hiểu ví dụ về lo và hi

Ví dụ - 4

đầu ra

The element is to be inserted at: 3
[23, 40, 61, 82, 82, 100, 12, 14]

Giải trình -

Vì lo và hi được truyền cho phương thức bisect_left() nên danh sách cần xem xét sẽ là a[2. 7] tương ứng với [23, 40, 61, 82, 82, 100, 12, 14]. Bisect_left tìm chỉ mục i trong lát này và sau đó trả về chỉ mục el dựa trên toàn bộ danh sách

  • insort_right(a, x, lo=0, hi=Không)

Nó hoạt động giống như insort_left(), ngoại trừ việc nó sử dụng hàm bisect_right() để tìm vị trí cần chèn giá trị x. Hãy hiểu ví dụ sau

Thí dụ -

đầu ra

[10, 20, 30, 40, 40, 40, 70, 60]

Nếu chúng ta sử dụng phương thức bisect_right, chúng ta sẽ nhận được kết quả tương tự

Đó là cách tốt nhất để sử dụng chức năng của Mô-đun Bisect. Cần xác định rằng độ phức tạp về thời gian của bisect_left và bisect_right là O(log(n)) do việc triển khai chúng sử dụng Thuật toán tìm kiếm nhị phân

Tuy nhiên, độ phức tạp về thời gian của insort_left và insort_right phụ thuộc vào độ phức tạp của phương thức chèn. Độ phức tạp thời gian của các phương pháp này là O(n)

Trong các ví dụ trên, chúng tôi đã sử dụng các số nguyên, nhưng chúng tôi cũng có thể sử dụng danh sách các số thực hoặc chuỗi

Nhưng nếu chúng ta sử dụng một bộ hoặc một chuỗi thì sao? . Nhưng nếu chúng ta cố gắng sử dụng insort_left và insort_right trên một chuỗi hoặc bộ, chúng ta sẽ gặp lỗi. Bởi vì các bộ dữ liệu và chuỗi là các đối tượng bất biến, các đối tượng này không triển khai phương thức chèn, phương thức này sửa đổi một đối tượng bất biến dưới dạng danh sách tại chỗ

bisect_right và insort_right có bí danh, vì vậy bisect_right có thể được gọi là bisect và insort_right là insort

Các vấn đề liên quan đến mô-đun Bisect

Hãy giải quyết một số vấn đề thú vị bằng cách sử dụng mô-đun chia đôi

Vấn đề - Viết chương trình Python để tìm ba số nguyên có tổng bằng 0 trong một mảng đã cho bằng Tìm kiếm nhị phân (chia đôi)

Thí dụ -

đầu ra

[[-40, 0, 40], [-20, -20, 40], [-20, 0, 20]]
[[-6, 1, 5], [-6, 2, 4]]

Vấn đề -2. Viết chương trình Python để tìm sự xuất hiện đầu tiên của một số đã cho trong danh sách đã sắp xếp bằng cách sử dụng Tìm kiếm nhị phân (chia đôi)

Giải pháp

đầu ra

First occurrence of 3 is present at index 2

Vấn đề - 3. Viết chương trình Python để tìm vị trí chỉ mục của lần xuất hiện cuối cùng của một số đã cho trong danh sách đã sắp xếp bằng cách sử dụng Tìm kiếm nhị phân (bisect)

Thí dụ -

đầu ra

Last occurrence of 3 is present at index 3

Phần kết luận

Trong hướng dẫn trên, chúng ta đã thảo luận chi tiết về mô-đun bisect và các phương thức của nó. Chúng ta đã xem một số ví dụ và tìm hiểu về các phương thức bisect_right và bisect_left. Mô-đun này được sử dụng để giải quyết các vấn đề liên quan đến tìm kiếm nhị phân

Phương thức bisect trong Python là gì?

Mục đích của thuật toán Bisect là để tìm một vị trí trong danh sách mà một phần tử cần được chèn vào để giữ cho danh sách được sắp xếp . Python theo định nghĩa của nó cung cấp các thuật toán chia đôi bằng cách sử dụng mô-đun “chia đôi” cho phép giữ danh sách theo thứ tự được sắp xếp sau khi chèn từng phần tử.

Bisect có được cài đặt sẵn trong Python không?

LƯU Ý. Bisect Module được cài đặt sẵn với các bản phân phối Python .

Insort là gì?

Phương thức insort() chèn một phần tử mới vào danh sách Python đã được sắp xếp sẵn . Nếu danh sách đã có các phần tử hiện có làm phần tử mới thì phần tử mới được chèn vào bên phải của phần tử hiện có cuối cùng đó. Các hàm insort() và insort_right() hoạt động theo cùng một cách.