Cho một mảng arr có n phần tử được sắp xếp tăng dần, mỗi phần tử chỉ xuất hiện một lần trong mảng. Viết chương trình tìm tất phần tử có giá trị bằng vị trí trong mảng. Nếu không có phần tử nào thoả in ra “khong ton tai”.
Cách 1: Linear search
Linear search là thuật toán tìm kiếm tuần tự đơn giản. Chúng ta sẽ duyệt tuần từ các phần tử trong mảng rồi kiểm tra xem nếu giá trị bằng vị trí thì xuất kết quả.
public class Main {
public static int fixedPointLinearSearch(int[] arr, int n) {
for (int i = 0; i < n; i++) {
if (arr[i] == i)
return arr[i];
}
return -1;
}
public static void main(String[] args) {
int[] arr = {-1, 0, 2, 4, 5, 6, 7};
int pos = fixedPointLinearSearch(arr, arr.length);
System.out.println(pos == -1 ? "Khong ton tai" : pos);
}
}
Output: 2
Độ phức tạp: O(n)
Cách 2: Binary search
Mảng ta nhận được là mảng tăng dần, nên ta hoàn toàn có thể sử dụng binary search để tăng tốc độ tìm kiếm nhé.
public class Main {
public static int fixedPointBinarySearch(int[] arr, int n) {
int l = 0, r = n - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == m ) {
return m;
}
if (arr[m] < m) {
l = m + 1;
} else {
r = m - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {-1, 0, 2, 4, 5, 6, 7};
int pos = fixedPointBinarySearch(arr, arr.length);
System.out.println(pos == -1 ? "Khong ton tai" : pos);
}
}
Output: 2
Độ phức tạp: O(log(n)).
Source code: source
Link tham khảo: https://www.geeksforgeeks.org/find-a-fixed-point-in-a-given-array/