Thuật Toán Tìm Kiếm 2 Con Trỏ - Binary Search đã Là Nhanh Nhất ?

Để giải quyết một bài toán trong lập trình, chúng ta có thể có nhiều cách, thuật toán để giải quyết. Tuy nhiên, không phải bài toán nào cũng có thể tối ưu trong 1 thuật toán nhất định. Trong bài viết này, chúng ta hãy cùng nhau nhìn qua các cách để giải quyết một bài toán tìm kiếm nho nhỏ và so sánh ưu nhược điểm giữa chúng nhé.

Bài toán

Cho một dãy số gồm N số nguyên khác nhau đã sắp xếp và một giá trị T, viết hàm in ra số nguyên A, B trong mảng sao cho A + B = T. Nếu không có 2 số nào thỏa mãn, in ra "NOT FOUND".

Hướng giải quyết 1: Duyệt trâu bò - Brute Force

Brute Force là một thuật toán vét cạn, thuật toán này sẽ chạy tất cả các trường hợp có thể có để giải quyết một vấn đề nào đó (Bao gồm cả trường hợp đúng và các trường hợp sai hay còn gọi là trường hợp dư thừa) Riêng với bài toán của chúng ta, thì thuật toán được đưa ra như sau:

• Duyệt 2 vòng lồng nhau các phần tử có trong dãy số để có được 2 số a, b
• Kiểm tra xem, nếu a + b = T và a != b thì a,b là 2 số được chọn

Trong Java, thuật toán sẽ được cài đặt như sau

void search(int[] array, int t) { for (int a : array) { for (int b : array) { if (a != b && a + b == t) { System.out.println("" + a + " " + b); return; } } } System.out.println("NOT FOUND"); }

Với cách sử dụng thuật toán này, độ phức tạp sẽ tính được là O(n2)

• Ưu điểm: Thuật toán đơn giản, cài đặt nhanh
• Nhược điểm: Độ phức tạp lớn, tính toán trong khoảng thời gian lâu với n đủ lớn (1000 phần tử trở lên)

Như vậy thuật toán này sẽ thích hợp sử dụng khi số phẩn tử trong dãy không quá nhiều

Hướng giải quyết 2: Tìm kiếm nhị phân - Binary Search

Thuật toán tìm kiếm nhị phân hoạt động trên các mảng đã được sắp xếp. Hoạt động theo các trình tự:

• So sánh một phần tử đứng chính giữa mảng với giá trị cần tìm.
• Nếu bằng nhau, vị trí của nó trong mảng sẽ được trả về. Nếu giá trị cần tìm nhỏ hơn phần tử này, quá trình tìm kiếm tiếp tục ở nửa nhỏ hơn của mảng.
• Nếu giá trị cần tìm lớn hơn phần tử ở giữa, quá trình tìm kiếm tiếp tục ở nửa lớn hơn của mảng. Bằng cách này, ở mỗi phép lặp thuật toán có thể loại bỏ nửa mảng mà giá trị cần tìm chắc chắn không xuất hiện

Trong Java, thuật toán sẽ cài đặt như sau:

void search(int[] array, int t) { for (int i = 0; i < array.length; i++) { int position = binarySearch(array, 0, array.length, t - array[i]); if (position != -1 && position != i) { System.out.println("" + array[i] + " " + array[position]); return; } } System.out.println("NOT FOUND"); }

Trong đó hàm tìm kiếm nhị phân sẽ được viết ra thành hàm khác như sau

int binarySearch(int array[], int left, int right, int target) { if (left > right) return -1; int mid = left + (right - left) / 2; if (array[mid] == target) return mid; if (array[mid] > target) return binarySearch(array, left, mid - 1, target); return binarySearch(array, mid + 1, right, target); }

Với cách sử dụng thuật toán này, độ phức tạp sẽ tính được là O(nLog(n))

• Ưu điểm: Tìm kiếm nhanh
• Nhược điểm: Cài đặt phức tạp

Vậy đến đây, chúng ta đã có thể kết luận rằng thuật toán BinarySearch đã nhanh nhất với bài toán đưa ra chưa nhỉ?

Hướng giải quyết 3: Tìm kiếm bằng 2 con trỏ - Two Pointer

Thuật toán tìm kiếm bằng 2 con trỏ hoạt động bằng cách sử dụng 2 con trỏ để duyệt phần tử cùng một thời điểm, tăng hiệu suất tìm kiếm Cụ thể, với bài toán này, thuật toán được đưa ra như sau:

• Đặt 1 con trỏ, bắt đầu duyệt từ phần tử đầu tiên trở đi
• Đặt 1 con trỏ, bắt đầu duyệt từ phần tử cuối cùng trở về
• So sánh tổng giá trị của 2 phần tử tại vị trí hiện tại các con trỏ
• Nếu tổng < giá trị tìm kiếm, dịch con trỏ đầu tiên lên 1 vị trí
• Nếu tổng > giá tị tìm kiếm, dịch con trỏ thứ 2 về 1 vị trí
• Làm như vậy đến khi tìm kiếm được giá trị hoặc là 2 con trỏ gặp nhau

Trong Java, thuật toán sẽ được cài đặt như sau

void searchPointer(int[] array, int t) { int left = 0, right = array.length - 1; while (left < right) { int sum = array[left] + array[right]; if (sum == t) { System.out.println("" + array[left] + " " + array[right]); return; } if (sum < t) left++; else right--; } System.out.println("NOT FOUND"); }

Với cách sử dụng thuật toán này, độ phức tạp sẽ tính được là O(n)

• Ưu điểm: Tìm kiếm nhanh, thuật toán không quá phức tạp
• Nhược điểm: Phạm vi áp dụng không rộng, chỉ áp dụng tốt với những dạng bài toán tìm kiếm 2 số trên mảng đã sắp xếp

Kết luận

Trên thực tế, bài toán lập trình mà chúng ta cần giải quyết sẽ không phải lúc nào cũng rõ ràng và đơn giản như này.

Đôi khi việc tìm kiếm 1 phần tử hay 2 phần tử chỉ là một bài toán con, một bước nhỏ trong bài toán lớn. Chính vì vậy, việc tối ưu các bước nhỏ này rất cần thiết.

Mong rằng trong số các thuật toán trên sẽ giúp các bạn có nhiều lựa chọn hơn khi đối mặt với vấn đề của mình. Chúc mọi người code tốt.