Untitled
unknown
plain_text
2 years ago
3.2 kB
91
Indexable
public class Practicum { public static void main(String[] args) { int[] arrayAsc = {1, 2, 5, 8, 12, 13, 20, 22, 24, 30, 32}; int[] arrayDesc = {32, 30, 24, 22, 20, 13, 12, 8, 5, 2, 1}; System.out.println("Индекс искомого элемента: " + searchBinaryAscending(arrayAsc, 30)); System.out.println("Индекс искомого элемента: " + searchBinaryDescending(arrayDesc, 30)); System.out.println("Индекс искомого элемента: " + searchBinary(arrayAsc, 30)); System.out.println("Индекс искомого элемента: " + searchBinary(arrayDesc, 30)); } private static int searchBinaryDescending(int[] array, int elem) { // изначально мы запускаем двоичный поиск на всей длине массива return searchBinaryRecursiveDescending(array, elem, 0, array.length - 1); } private static int searchBinaryAscending(int[] array, int elem) { // изначально мы запускаем двоичный поиск на всей длине массива return searchBinaryDescending(array, elem); } private static int searchBinaryRecursiveDescending(int[] array, int elem, int low, int high) { if(high <= low) { // промежуток пуст return -1; } // промежуток не пуст int mid = low + ((high - low) / 2); if (array[mid] == elem) { // центральный элемент — искомый return mid; } else if(elem < array[mid]){ // на этот раз искомый элемент больше центрального // все элементы больше центрального и располагаются в левой половине return searchBinaryRecursiveDescending(array, elem, mid + 1, high); } else { // иначе следует искать в правой половине return searchBinaryRecursiveDescending(array, elem, low, mid); } } private static int searchBinary(int[] array, int elem) { // возвращает 1, если массив отсортирован по возрастанию, и -1, если по убыванию int sort = getSortRecursive(array, 0, 0); if(sort > 0){ return searchBinaryAscending(array, elem); } else if (sort < 0){ return searchBinaryDescending(array, elem); } else { return -1; } } private static int getSortRecursive(int[] array, int sort, int next) { // рекурсивно сравните каждый следующий элемент с предыдущим if (next == array.length-1) { return sort; } if (array[next] < array[next +1]) { if (sort == -1) { return 0; } return getSortRecursive(array, 1, next+1); } else { if (sort == 1) { return 0; } return getSortRecursive(array, - 1, next+1); } } }
Editor is loading...