algorithm - 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 = 4 时，我正在尝试对 k 元搜索算法执行相同的操作，但我找不到可以分析的伪代码。任何帮助或指导将不胜感激。

Answer 1

经过几天的努力，我提出并再次回答了另一个问题。在互联网的帮助下，我编写了一个可以与 acm 库一起正常工作的 java 代码。我们正在寻找的数字是 x，j 是我们集合的最后一个索引，数组是递增的。通过更改这些参数，我们可以使用四进制算法在任何数组中查找任何数字。

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);

    }






}