Алгоритм четвертичного поиска

Question

Я должен написать код для четвертичного алгоритма поиска. Единственное описание, которое я получил, это то, что это модификация алгоритма бинарного поиска, но вместо разделения массива на два он разбивает массив на четыре.

Я немного смущен относительно того, как именно такой поиск должен работать. Я искал высокий и низкий для псевдокода или даже просто видео на YouTube, объясняющее/визуализирующее, как работает этот поиск, но я ничего не смог найти.

У кого-нибудь есть псевдокод или быстрое и грязное объяснение того, как этот алгоритм поиска может работать?

Спасибо!

Answer 1

QuaternarySearch(A[0. . n-1], value, low, high) 
    while high ≥ 1 
     p1/4 = low + ((high – low)/4)   //first quarter point 
     p1/2 = low + ((high – low)/2)   //second quarter point 
     p3/4 = low + (3(high – low)/4)  //third quarter point 
     if A[p1/4] = value 
      return A[p1/4] 
     else if A[p1/2] = value 
      return A[p1/2] 
     else if A[p3/4] = value 
      return A[p3/4] 
     else if A[p1/4] > value 
      return QuaternarySearch(A, value, low, p1/4-1) 
     else if A[p1/2] > value 
      return QuaternarySearch(A, value, p1/4+1, p1/2-1) 
     else if A[p3/4] > value > A[p1/2] 
      return QuaternarySearch(A, value, p1/2+1, p3/4-1) 
else      //if A[p3/4] < value 
      return QuarterSearch(A, value, p3/4 + 1, high)