Trong bài viết này, chúng tôi được đưa ra một vấn đề, chúng tôi được cung cấp một mảng và có hai loại truy vấn mà chúng tôi cần trả lời.
- Loại 0 - chúng ta phải tính số phần tử lớn hơn hoặc bằng x (giá trị đã cho).
- Loại 1 - chúng ta phải tính số phần tử lớn hơn x (giá trị đã cho).
Đây là một ví dụ đơn giản -
Đầu vào:arr [] ={10, 15, 30, 40, 45} và Q =3 Truy vấn 1:0 50 Truy vấn 2:1 40 Truy vấn 3:0 30 Đầu ra:0 1 3 Phép toán:x =50, q =0:Không có phần tử nào lớn hơn hoặc bằng 50.x =40, q =1:45 lớn hơn 40.x =30, q =0:ba phần tử 30, 40, 45 lớn hơn hoặc bằng 30. Phương pháp tiếp cận để tìm ra giải pháp
Chúng ta có thể sử dụng hai phương pháp khác nhau để tìm ra giải pháp. Đầu tiên, chúng tôi sẽ sử dụng giải pháp brute force và sau đó kiểm tra xem nó có thể hoạt động với các ràng buộc cao hơn hay không. Nếu không, thì chúng tôi tiến hành tối ưu hóa giải pháp của mình.
Phương pháp tiếp cận vũ phu
Trong cách tiếp cận này, chúng tôi sẽ duyệt qua mảng cho tất cả q truy vấn và tìm các số thỏa mãn các điều kiện đã cho.
Ví dụ
#include using namespace std; void query (int * arr, int n, int type, int val) {int count =0; // answer if (! type) {// khi yêu cầu truy vấn kiểu 0 for (int i =0; i =val) count ++; }} else {// khi truy vấn loại 1 được hỏi for (int i =0; i val) count ++; }} cout < Đầu ra
013
Trong cách tiếp cận ở trên, chúng tôi chỉ đơn giản là duyệt qua mảng và tính toán câu trả lời cho các truy vấn; cách tiếp cận này đang hoạt động đối với các ví dụ đã cho, nhưng nếu chúng ta gặp phải ràng buộc cao hơn, cách tiếp cận này sẽ không thành công vì độ phức tạp thời gian tổng thể của chương trình là O (N * Q) trong đó N là kích thước mảng của chúng ta và Q là số lượng truy vấn vì vậy bây giờ chúng tôi sẽ tối ưu hóa cách tiếp cận này để nó cũng hoạt động với các ràng buộc cao hơn.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng tôi sẽ sử dụng tìm kiếm nhị phân để tìm giới hạn trên và giới hạn dưới của giá trị đã cho. Trước tiên, chúng tôi sắp xếp mảng của mình bằng cách sử dụng tìm kiếm nhị phân, sau đó áp dụng các hàm giới hạn dưới và giới hạn trên cho phù hợp.
Ví dụ
#include using namespace std; void Lowerbound (int * arr, int n, int val) {int l =-1, r =n; while (r - l> 1) {// tìm kiếm nhị phân câu trả lời int mid =(l + r) / 2; if (arr [mid]> =val) r =mid; khác l =giữa; } if (r ==n) // nếu r không chuyển động thì có nghĩa là không có phần tử nào thỏa mãn điều kiện cout <<"0 \ n"; else cout < 1) {// tìm kiếm nhị phân câu trả lời int mid =(l + r) / 2; if (arr [mid]> val) r =mid; khác l =giữa; } if (r ==n) // nếu r không chuyển động thì có nghĩa là không có phần tử nào thỏa mãn điều kiện cout <<"0 \ n"; else cout < Đầu ra
012
Đoạn mã trên hoạt động trên một tìm kiếm nhị phân làm giảm đáng kể độ phức tạp về thời gian của chúng ta. Do đó, độ phức tạp cuối cùng của chúng ta trở thành O (NlogN) , trong đó N là kích thước mảng của chúng ta.
Giải thích về đoạn mã trên
Trong cách tiếp cận này, chúng tôi sẽ sử dụng tìm kiếm nhị phân để tìm giới hạn trên và giới hạn dưới của giá trị đã cho. Bây giờ đối với tìm kiếm nhị phân, trước tiên chúng ta sắp xếp mảng của mình vì nó chỉ hoạt động với các mảng được sắp xếp. Chúng tôi tạo hàm giới hạn dưới và giới hạn trên để giúp chúng tôi tìm số đầu tiên tương ứng thỏa mãn các điều kiện loại 0, loại 1, ngay bây giờ khi chúng tôi đã sắp xếp mảng. Chúng tôi đã tìm thấy số đầu tiên giúp điều kiện, vì vậy các phần tử sau phần tử này cũng tuân theo điều kiện, vì vậy chúng tôi in ra sự khác biệt của chỉ số của phần tử này với N (kích thước của mảng của chúng tôi).
Kết luận
Trong bài viết này, chúng tôi giải quyết một vấn đề để giải quyết các Truy vấn lớn hơn và không nhỏ hơn bằng cách sử dụng tìm kiếm nhị phân. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.