Cho một mảng arr được sắp xếp tăng dần và một phần tử x. Viết chương trình tìm phần tử nhỏ nhất trong mảng lớn hơn hoặc bằng x.
Cho ví dụ
Input: arr[] = {1, 2, 3, 4, 6, 9}
X = 5 => output: 6
X = 0 => output: 1
X = 10 => output: khong ton tai
Cách 1: Linear search
Linear search là thuật toán tìm kiếm đơn giản mà ai học lập trình cũng phải biết đến.
Các bước thực hiện:
| Duyệt từng phần tử arr[i] của mảng if (arr[i] >= x) return i Return -1 nếu không có phần tử nào thoả. |
public class Main {
public static int ceilingLinearSearch(int[] arr, int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] >= x)
return i;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 6, 7};
int pos = ceilingLinearSearch(arr, arr.length, 5);
System.out.println(pos == -1 ? "Khong ton tai" : arr[pos]);
}
}
Output: 6
Độ phức tạp: O(n)
Cách 2: Binary search
Ở cách 1, chúng ta sử dụng linear search để giải bài toán này, thế nhưng để ý rằng có một dữ liệu quan trọng mà đề cho chúng ta chưa sử dụng là “mảng được sắp xếp tăng dần”. Binary search là thuật toán tìm kiếm trên mảng được sắp xếp, với bài này chúng ta cần custom lại một chút nhé.
Ý tưởng chính của binary search xoay quanh điểm nằm giữa tạm gọi là mid. Trong quá trình tìm kiếm nếu arr[mid] == x thì quá tốt rồi, đó cũng là kết quả của đề bài chúng ta mong muốn.
Thế nhưng, sau khi kết thúc binary mà vẫn không có giá trị nào bằng x thì sao? chúng ta sẽ còn trường hợp lớn hơn x nhỏ nhất.
Nhận xét thấy arr[mid] luôn có tính chất: arr[mid] <= x. Ở trường hợp này loại “=” vì đã kết thúc quá trình tìm kiếm. Cộng thêm mảng tăng dần => arr[mid + 1] là giá trị nhỏ nhất lớn hơn x.
Các bước thực hiện:
| B1: Binary search cho mảng arr if binary return kết quả thì kết thúc Ngược lại if mid == 0 return 0 else if mid == n return -1 else return mid + 1 |
public class Main {
public static int ceilingBinarySearch(int[] arr, int n, int x) {
int l = 0, r = n - 1;
int m = -1;
while (l <= r) {
m = l + (r - l) / 2;
if (arr[m] == x) {
return m;
}
if (arr[m] < x) {
l = m + 1;
} else {
r = m - 1;
}
}
if (m == 0)
return 0;
if (m == n - 1)
return -1;
return m + 1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 6, 7};
int pos = ceilingBinarySearch(arr, arr.length, 6);
System.out.println(pos == -1 ? "Khong ton tai" : arr[pos]);
}
}
Output: 6
Độ phức tạp: O(Log(n))
Full source code: Source
Nguồn tham khảo: geeksforgeeks