创建了我自己的二进制搜索版本，不明白为什么它比常规方法要快？

Question

向阅读这篇文章的所有人问好。我最近刚毕业，现在基本上要复习所学到的每个概念，以刷新自己的记忆或提高自己的技能，以便我可以申请公司并被录用。我的第一个复习课程将进行二进制搜索，因此我决定编写自己的版本，而不考虑常规方法。我碰巧写了以下代码，在其中我将常规方法的时间复杂度与自己的二进制搜索版本进行了比较。 尽管，我的二进制搜索似乎同时集成了线性搜索和二进制搜索，但是它似乎比常规方法要快一些，我只是不明白为什么。当关键字大于中间元素时，将使用线性搜索，这似乎实际上会增加搜索的时间复杂度。您可以在“ myBinarySearch”方法中找到条件的情况下，在我的代码中找到其他代码。即使搜索了数组的15,000个整数，我的版本仍然更快。

有人可以向我解释为什么我的版本要快得多吗？与我的二进制搜索版本相比，以下是常规方法。我的版本仅在搜索不存在且过度使用的键（例如，搜索16,000）时变慢。它必须是多余的，因为搜索15,001确实会导致更快的返回-1的时间。

我的结论是因为我只使用一个变量，而不是在常规方法中使用3个变量，而常规方法是在遍历数组时检查和/或更新这些变量。虽然，在我的方法中最后一个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> 1000，即使您尝试n = 500。