通过将数组切成两半来查找元素的搜索方法（Java）

Question

我正在做一个作业。我必须创建一个在数组中搜索特定 int 的方法。假设数组已经按从最低数到最高数排序。但条件是它必须通过将所述数组切成两半并检查目标数字位于哪一半来进行搜索，然后再次将所述一半切成两半，依此类推。

我们也被要求不要使用递归方法。

这是我想出的代码，但我没有看到我的错误，任何帮助更好地理解问题的帮助都非常感激！

public static boolean SearchInHalf(int[] array, int targetint)

{

    int fin = array[array.length-1]; 

    int init = array[0];

    int range = fin-init;

    if ( targetint>array[array.length-1] || targetint< array[0])

    {

        return false;

    }

    while (range>=2)

    {

        int half = array[range/2];

        if (targetint>half)

        {

            init = half;

            range = fin-init;

            half = array[range/2];

        }

        else if (targetint<half)

        {

            fin = half;

            range = fin-init;

            half = array[range/2];

        }

        else if (targetint==half || targetint==fin || targetint==init)

        {

            return true;

        }

    }

    return false;

}

Answer 1

您的问题称为“二分搜索”。为了使二分搜索工作，数组中的元素必须已经排序（这是您的情况，让我们假设升序）。二分查找首先将键与数组中间的元素进行比较：如果key小于中间元素，则只需要在数组的前半部分继续查找key。如果key大于中间元素，则只需要在数组的后半部分继续查找key。如果键等于中间元素，则搜索以匹配结束。所以二分查找法每次比较后至少消除数组的一半。假设您将在静态主函数中调用此方法：public static int binarySearch(int[] list, int key) {&nbsp; int low = 0;&nbsp; int high = list.length - 1;&nbsp; while(high >= low) { //search array until there is a single element left&nbsp; &nbsp; int mid = (low + high) / 2; //mark middle index&nbsp; &nbsp; if (key < list[mid]) //if key is smaller than the middle element..&nbsp; &nbsp; &nbsp; high = mid - 1;&nbsp; //new high is the middle element&nbsp; &nbsp; else if (key == list[mid]) //if key=middle element --> voila!&nbsp; &nbsp; &nbsp; return mid; //returns the index of searched element if it is in your array&nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; low = mid + 1; //if key is greater than the middle element new low is middle element&nbsp; }&nbsp; return –low - 1;&nbsp; //high < low, key not found}

Answer 2

像这样解决了：while (true) {&nbsp; &nbsp; if (targetint>array[array.length-1] || targetint<array[0])&nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; int middleInt = array[Math.round(array.length/2)];&nbsp; &nbsp; if (middleInt == targetint) {&nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; } else if (targetint<middleInt) {&nbsp; &nbsp; &nbsp; &nbsp; int[] firstHalf = new int[array.length/2];&nbsp; &nbsp; &nbsp; &nbsp; System.arraycopy(array, 0, firstHalf, 0, firstHalf.length);&nbsp; &nbsp; &nbsp; &nbsp; array = firstHalf;&nbsp; &nbsp; } else if (targetint>middleInt) {&nbsp; &nbsp; &nbsp; &nbsp; int[] secondHalf = new int[array.length/2];&nbsp; &nbsp; &nbsp; &nbsp; System.arraycopy(array, array.length/2, secondHalf, 0, secondHalf.length);&nbsp; &nbsp; &nbsp; &nbsp; array = secondHalf;&nbsp; &nbsp; } else if(array.length == 1)&nbsp; &nbsp; &nbsp; &nbsp; return false;}