當k = 4時k進制搜索算法的運算次數？

Question

我正在分析搜索算法的複雜性。例如對於僞代碼在下面給出的二分搜索，我可以寫出

循環外的5次操作（3次賦值，1次減法，1次比較）。

每次循環運行時的7次操作（2次增加，1次除數，2次比較，2次賦值）。

int binary_search(int x, int a[], int n) 
{ 
int i, j, location; 
int m; 
i = 0; 
j = n-1; 
while (i < j) { 
m = (i + j)/2; 
if (x > a[m]) i = m+1; 
else j = m; 
} 
if (x == a[i]) location = i; 
else location = -1; 
return location; 
} 

我想對k元搜索算法當k = 4這樣做，但我無法找到一個僞代碼，我可以analyize。任何幫助或指導將不勝感激。

Answer 1

另一個問題，我問了幾次鬥爭後，我又回答了。通過互聯網的一些幫助，我寫了一個可以在acm庫中正常工作的java代碼。我們要查找的數字是x，j是我們集合的最後一個索引，數組的順序是遞增的。通過改變這些參數，我們可以使用4元算法在任何數組中查找任意數字。

import java.util.Arrays; 

import acm.program.*; 


public class quartersearch extends ConsoleProgram { 


    public void run() { 

     int i = 0; 
     int j = 15; 
     int location; 
     int x = 6; 

     int[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}; 

     println(a[2]); 

     while (i < j) { 
      int l = (j + 3*i) /4 ; // 1st divisor 
      int m = (j + i)/2; // 2nd divisor 
      int u = (3*j + i)/4; // 3rd divisor 
      if(x > a[u]) { 
       i = u + 1; 
      } else if (x > a[m] && x <= a[u]) { 
       i = m + 1; 
       j = u; 
      } else if (x > a[l] && x <= a[m]) { 
       i = l + 1; 
       j = m; 
      } else { 
       j = l; 
      } 
     } 


     int k = (i+j)/2; 
     if (a[i] == x) { 
      location = i; 
     } else if (a[k] == x) { 
      location = k; 
     } else if (a[j] == x) { 
      location = j; 
     } else { 
      location = 0; 
     } 

     println(location); 

    } 






}