Двоичный поиск 1/4 модификация

Question

Моя задача - написать модификацию алгоритма бинарного поиска 1/4 - 3/4, в которой первый элемент, сравниваемый при поиске элемента в списке, является элементом «поворота», который находится на расстояние 1/4 от один конец списка (при условии, что выбранный конец является началом «остающегося» списка ). Если нет совпадения (элемент «pivot» не равен ключу поиска) и , если часть списка, которую следует изучить дальше для поиска, составляет 1/4 часть списка, перейдите к той же стратегии. Всякий раз, когда часть списка , который должен быть дополнительно исследован для поиска, имеет размер 3/4, переключитесь на двоичный поиск один раз и вернитесь к стратегии 1/4th-3/4th. Мой код здесь, но он не работает, и я не знаю, даже если я делаю это правильно:

public static int ThreeFour(int[] Array,int item) 
    { 
     int counter =0; 
     int high=Array.length-1; 
     int low=0; 
     int pivot = 0; 

     boolean split = true; 
     boolean last =true; 

     while(high >= low) { 
     if(split){ 
      pivot = (high+low)/4; 
      last=true;} 
     else 
     { pivot = (high+low)/2; 
     split=true; 
     last=false; 
     } 

     if(Array[pivot] == item) 
     { counter++; 
     System.out.println("Pivot"+pivot); 
     return counter; 
     } 

     if(Array[pivot] < item) { 
      low = pivot + 1; 
      counter++; 
     } 

     if(Array[pivot] > item) { 
      high = pivot - 1; 
      counter++; 
      if (last) 
       split=false; 
     } 
     } 
     return 0; 
    } 

Это не работает, может быть, есть стратегия проще сделать это? Самая трудная часть, чтобы сделать его вспомнить, что он уже расщепляется пополам один раз:/

Answer 1

Ваша формула для определения поворота неправильно для 3/4 раскола. Если вы хотите разделить интервал между low и high в какой-то момент c с 0 <= c <=1, вы получите:

pivot = low + c * (high - low) 
     = (1 - c) * low + c * high 

Это Виль дать вам low для c == 0, high для c == 1 и для 3/4 раскола:

pivot = 0.75 * low + 0.25 * high 

или с целочисленной арифметики:

pivot = (3 * low + high)/4 

В частности, коэффициенты для low и high должны подвести до 1.

Я также думаю, что ваша функция имеет логическую ошибку: Вы возвращаетесь глубина рекурсии, которая не имеет никакого значения для массива. Вы должны вернуть опорный элемент, т. Е. Индекс массива, в котором находится элемент. Это также означает, что вы не можете вернуть 0 при ошибке, потому что это допустимый индекс массива. Верните нелегальный индекс, например -1, чтобы указать, что элемент не найден.