时间戳

首页 > 解决方案 > 通过将数组分成两半来查找元素的搜索方法（Java）

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

问题描述

我正在做一个任务。我必须创建的是一种在数组中搜索特定 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;

}

标签： javaarraysalgorithmsearch

解决方案

您的问题被称为“二进制搜索”。要使二进制搜索起作用，数组中的元素必须已经排序（这是您的情况，我们假设升序）。二分查找首先将键与数组中间的元素进行比较：

  • 如果key小于中间元素，则只需要在数组的前半部分继续搜索key。
  • 如果key大于中间元素，则只需要在数组的后半部分继续搜索key。
  • 如果键等于中间元素，则搜索以匹配结束。

所以二分查找法在每次比较后至少消除了一半的数组。假设您将在静态主函数中调用此方法：

public static int binarySearch(int[] list, int key) {
  int low = 0;
  int high = list.length - 1;

  while(high >= low) { //search array until there is a single element left
    int mid = (low + high) / 2; //mark middle index
    if (key < list[mid]) //if key is smaller than the middle element..
      high = mid - 1;  //new high is the middle element
    else if (key == list[mid]) //if key=middle element --> voila!
      return mid; //returns the index of searched element if it is in your array
    else
      low = mid + 1; //if key is greater than the middle element new low is middle element
  }
  return –low - 1;  //high < low, key not found
}

推荐阅读