Thuật toán tìm kiếm nhị phân là một trong các thuật toán sắp xếp được sử dụng rất nhiều trong thực tế.
Tìm kiếm là một phần không thể thiếu của mọi ứng dụng. Tính năng tìm kiếm cho phép người sử dụng nhanh chóng truy vấn và tìm kiếm các bản ghi theo mong muốn. Và một công cụ tìm kiếm nổi tiếng nhất hàng ngày chúng ta vẫn thường sử dụng đó là Google search.
Bài viết này mình sẽ giới thiệu cho các bạn một thuật toán tìm kiếm tối ưu áp dụng đối với trường hợp dữ liệu số đã sắp xếp.
Cho một mãng có n phân tử đã sắp xếp, viết chức năng để tìm kiếm phần tử x trong mãng này.
Giải thuật đơn giản nhất cho bài toán này là sử dụng linear search(tìm kiếm tuyến tính). Đi qua từng phần tử của mảng để tìm x. Thuật toán này trong trường hợp xấu nhất cho độ phức tạp là O(n).
Code minh họa tình kiếm tuyến tính
package gatostudy.com.sort;
public class LinearSearch {
public static int search(int arr[], int x)
{
int n = arr.length;
for(int i = 0; i < n; i++)
{
if(arr[i] == x)
return i;
}
return -1;
}
public static void main(String args[])
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int result = search(arr, x);
if(result == -1)
System.out.print(“Element is not present in array”);
else
System.out.print(“Element is present at index ” + result);
}
}
Một cách tiếp cận nữa để thực hiện tìm kiếm là sử dụng Binary Search.
Binary Search: Tìm kiếm nhị phân trên 1 mãng đã sắp xếp giảm độ phức tạp chỉ O(Log n)
Về cơ bản chúng ta sẽ loại bỏ được ½ các phân từ trong mảng sau 1 phép so sánh.
Các bước thực hiện.
- So sánh x với phân tử đứng giữa.
- Nếu x là số ở giữa thì return x.
- Nếu x lớn hơn phần tử chính giữa thì x chỉ có thể ở phía bên phải của phần tử chính giữa.
- Ngược lại thì x sẽ ở phía bên trái phần tử chính giữa.
- Sử dụng đệ quy để tìm kiếm tương tự..
Code minh họa tìm kiếm nhị phân.
package gatostudy.com.sort;
// Java implementation of recursive Binary Search
class BinarySearch {
// Returns index of x if it is present in arr[l..
// r], else return -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r – l) / 2;
// If the element is present at the
// middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid – 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver method to test above
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, 0, n – 1, x);
if (result == -1)
System.out.println(“Element not present”);
else
System.out.println(“Element found at index ” + result);
}
}
