Viết một chương trình tìm kiếm phần tử x trong mảng. Biết rằng các phần tử liền kề trong mảng hơn kém nhau không quá k.
Cách đơn giản nhất là chúng ta duyệt từng phần tử và so sánh để tìm ra vị trí phần tử cần tìm. Đây là loại tìm kiếm đơn giản, được gọi là linear search.
Chúng ta quay lại với đề bài, ta thấy còn một dữ kiện chưa dùng đến là “Các phần tử liền kề hơn kém nhau không quá k”.
Ví dụ cho k = 5, thì ta có
arr[0] = 1
arr[1] có miền giá trị trong khoảng -4 đến 6
Dựa vào tính chất này, thấy rằng tại vị trí i trong mảng thì abs(arr[i] – x) là khoảng giá trị mà ta cần đạt để có giá trị bằng với x, ta lại có k là khoảng cách giá trị lớn nhất mà 2 phần tử liền kề có thể đạt được. Vậy thì nếu abs(arr[i] – x) = 2K hoặc 3K, thì theo bạn arr[i + 1] có thể là phần tử X được không?
Phần tử tiếp theo được nhảy tới để được tính theo công thức: i + Max(1, abs(arr[i] – x)/k)
public class Main {
public static void main(String[] args) {
int arr[] = {1, 3, 4, 6, 7, 9};
int x = 6;
int k = 2;
int n = arr.length;
int pos = search(arr, n, x, k);
if (pos == -1) {
System.out.println("Khong tim thay");
} else {
System.out.println("Phan tu tim thay tai: " + pos);
}
}
static int search(int arr[], int n, int x, int k) {
int i = 0;
while (i < n) {
if (arr[i] == x)
return i;
i = i + Math.max(1, Math.abs(arr[i]
- x) / k);
}
return -1;
}
}
Output: Phan tu tim thay tai: 3
Nguồn tham khảo: geeksforgeeks