java - 创建了我自己的二分搜索版本，不明白为什么它比常规方法更快？

Question

各位阅读这篇文章的人大家好。我最近毕业了，我基本上会复习我学到的每一个概念，以刷新我的内存或更好地提高我的技能，以便我可以申请公司并被雇用。我的第一次复习是二分搜索，我决定编写自己的版本，而不查看常规方法。我碰巧编写了以下代码，其中我将常规方法的时间复杂度与我自己的二分搜索版本进行了比较。 虽然，我的二分搜索似乎集成了线性搜索和二分搜索，但它似乎比常规方法更快，我只是不明白为什么。当键大于中间元素时使用线性搜索，这似乎实际上会增加搜索的时间复杂度。您可以在“myBinarySearch”方法中最后一个 else if 条件的代码中看到这一点。然而，即使在搜索数组的 15,000 个整数之后，我的版本仍然更快。

谁能向我解释一下为什么我的版本更快？下面是与我的二分搜索版本相比的常规方法。我的版本只是在搜索不存在的key且过度的时候比较慢，比如搜索16000。它一定是过多了，因为搜索 15,001 确实会导致返回 -1 的时间更快。

我得出的结论是，这是因为我只使用了一个变量，而不是在常规方法中使用 3 个变量，常规方法在循环数组时检查和/或更新这些变量。尽管如此，我的方法中最后一个 else if 语句中的线性搜索让我感到困惑，并让我想知道这如何不会增加时间复杂度。

public static void main(String[] args) {
    int[] array = new int[15000];
    File file; 
    BufferedReader br;
    try {
       file = new File("../Java/bin/IntroToJavaBook/largeArray.txt");
       br = new BufferedReader(new FileReader(file));
       String st;
       int i = 0;
       while((st = br.readLine()) != null) 
       {
           array[i] = Integer.parseInt(st);
           i++;
       }
    } catch (FileNotFoundException e) {
       e.printStackTrace();
    } catch (IOException e) {
       e.printStackTrace();
    } 

    int key = 4200;
    long startTime = System.nanoTime();
    System.out.println(binarySearch(array, key));
    long endTime = System.nanoTime();
    long duration = (endTime - startTime);
    System.out.println(duration);

    long startTime1 = System.nanoTime();
    System.out.println(myBinarySearch(array, key));
    long endTime1 = System.nanoTime();
    long duration1 = (endTime1 - startTime1);
    System.out.println(duration1);

}

static int binarySearch(int[] array, int key) {
    int low = 0;
    int high = array.length - 1;
    while (high >= low) 
    {
        int mid = (low + high) / 2; 
        if (key < array[mid])
        {
            high = mid - 1;
        }
        else if (key == array[mid])
        {
            return mid; 
        }
        else
        {
            low = mid + 1;
        }
    }
    return -1;
}

static int myBinarySearch(int[] array, int key) {
    int half = array.length/2;
    while(true)
    {
        if(half == 0 || half == array.length)
        {
            return -1;
        }
        else if(key < array[half])
        {
            half /= 2;
        }
        else if(key == array[half])
        {
            return half;
        }
        else if(key > array[half])
        {
            half = half + 1;
        }
    }
}

Answer 1

您将复杂性与速度混淆了。就复杂性而言，即使您使用 n=500 运行测试，n>1000。