对排序的字符串数组进行递归二分搜索

Question

我制作了一个长度为 10 的数组。每个插槽都有一个名称。我的目标是随机选择一个名称并进行二分搜索来找到它。我不明白它有什么问题，但如果您至少能给我一个提示，那将非常有帮助，谢谢。这是我的代码：    private int iRecursiveCalls = 0;    public void runRecursiveTest(){        String[] iArraySize = new String[10];        String[] aiNumbers = new String[iArraySize.length];        SecureRandom oRand = new SecureRandom();        iArraySize[0] = "John";        iArraySize[1] = "Max";        iArraySize[2] = "Kyle";        iArraySize[3] = "Sam";        iArraySize[4] = "Robert";        iArraySize[5] = "Alex";        iArraySize[6] = "Bob";        iArraySize[7] = "Daniel";        iArraySize[8] = "Felix";        iArraySize[9] = "Michael";        String iTarget = aiNumbers[oRand.nextInt(iArraySize.length)];        Arrays.sort(aiNumbers);        System.out.println("Target num: " + iTarget);        System.out.println("--- Begin Binary Search ---");        long lBegTime = System.nanoTime();        findNumbersBinarySearch(aiNumbers, iTarget, 0, iArraySize.length -1);        long lEndTime = System.nanoTime();        System.out.println("Elapsed time: " + (lEndTime - lBegTime));        System.out.println("Recursive calls: " + iRecursiveCalls);        System.out.println("--- End Binary Search ---");    }    private int findNumbersBinarySearch(String[] aiNumbers, String iTarget,                                        int iLow, int iHigh){        iRecursiveCalls++;        int iMiddle = (iHigh + iLow) / 2;        if(iTarget.equals(aiNumbers[iMiddle])){            return iMiddle;        }        else if(iTarget.compareTo(aiNumbers[iMiddle])>0){            return findNumbersBinarySearch(aiNumbers, iTarget,                    iMiddle + 1, iHigh);        }        else{            return findNumbersBinarySearch(aiNumbers, iTarget,                    iLow, iMiddle - 1);        }    }}我能做些什么来修复它？

Answer 1

您的算法不起作用，因为您正在对一个空数组进行索引、排序和传递给您的函数。您可能在iArraySize和之间感到困惑aiNumbers；这两个都是误导性的变量名称，因为您将字符串名称添加到iArraySize并且aiNumbers不包含数字。您的二分搜索函数名称和其他变量同样具有误导性；即使函数头采用数组，它们也使用单词Numbers和前缀 。iString[]

此外，如果在数组中找不到目标，您的代码将破坏调用堆栈。经典的二分查找会返回失败一次lo > hi；我想不出任何不包括base case 的理由。

另一个二分搜索问题是使用公式mid = (hi - lo) / 2 + lo。这避免了如果hi + lo > Integer.MAX_SIZE.

这段代码通过在整个过程中坚持一个数组来解决这些问题，使用更准确的变量名并且不会溢出堆栈：

import java.util.*;

import java.security.SecureRandom;

class Main {

    private static int recursiveCalls = 0;

    public static void main(String[] args) {

        runRecursiveTest();

    }

    public static void runRecursiveTest() {

        SecureRandom rand = new SecureRandom();

        String[] names = {

            "John",

            "Max",

            "Kyle",

            "Sam",

            "Robert",

            "Alex",

            "Bob",

            "Daniel",

            "Felix",

            "Michael"

        };

        String target = names[rand.nextInt(names.length)];

        Arrays.sort(names);

        System.out.println("Target string: " + target);

        System.out.println("--- Begin Binary Search ---");

        long begin = System.nanoTime();

        System.out.println(bisect(names, target, 0, names.length - 1));

        long end = System.nanoTime();

        System.out.println("Elapsed time: " + (end - begin));

        System.out.println("Recursive calls: " + recursiveCalls);

        System.out.println("--- End Binary Search ---");

    }

    private static int bisect(String[] arr, String target, int lo, int hi) {

        recursiveCalls++;

        if (lo > hi) { return -1; }

        int mid = (hi - lo) / 2 + lo;

        if (target.equals(arr[mid])) {

            return mid;

        }

        else if (target.compareTo(arr[mid]) > 0) {

            return bisect(arr, target, mid + 1, hi);

        }

        return bisect(arr, target, lo, mid - 1);

    }

}

输出：

Target string: Sam

--- Begin Binary Search ---

9

Elapsed time: 81385

Recursive calls: 4

--- End Binary Search ---