Это очень похоже на бинарный поиск, за исключением того, что если он не находит точный ключ, он возвращает ключ, который будет очень близок к предоставленному ключу.
Логика заключается в поиске до тех пор, пока не будет найден точный ключ или пока не останется ровно один ключ между старшим и нижним ключами при выполнении двоичного поиска.
Рассмотрим массив n [] = {1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
если вы ищете ключ: 2, то используйте алгоритм ниже
Шаг 1: высокий = 10, низкий = 0, средний = 5
Шаг 2: высокий = 5, низкий = 0, средний = 2
Шаг 3: высокий = 2, низкий = 0, мед = 1 На этом шаге будет найден точный ключ. Так что возвращается 1.
если вы ищете ключ: 3 (которого нет в массиве), используйте алгоритм ниже
Шаг 1: высокий = 10, низкий = 0, средний = 5
Шаг 2: высокий = 5, низкий = 0, средний = 2
Шаг 3: высокий = 2, низкий = 0, мед = 1
Шаг 4: высокий = 1, низкий = 0, на этом этапе высокий = низкий + 1, то есть больше нет элементов для поиска. Так что возвращается med = 1.
Надеюсь, это поможет ...
public static <T> int binarySearch(List<T> list, T key, Comparator<T> compare) {
int low, high, med, c;
T temp;
high = list.size();
low = 0;
med = (high + low) / 2;
while (high != low+1) {
temp = list.get(med);
c = compare.compare(temp, key);
if (c == 0) {
return med;
} else if (c < 0){
low = med;
}else{
high = med;
}
med = (high + low) / 2;
}
return med;
}
/** ------------------------ Example -------------------- **/
public static void main(String[] args) {
List<Integer> nos = new ArrayList<Integer>();
nos.addAll(Arrays.asList(new Integer[]{1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}));
search(nos, 2); // Output Search:2 Key:1 Value:2
search(nos, 3); // Output Search:3 Key:1 Value:2
search(nos, 10); // Output Search:10 Key:5 Value:10
search(nos, 11); // Output Search:11 Key:5 Value:10
}
public static void search(List<Integer> nos, int search){
int key = binarySearch(nos, search, new IntComparator());
System.out.println("Search:"+search+"\tKey:"+key+"\tValue:"+nos.get(key));
}
public static class IntComparator implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
}