Java：子阵列和二进制搜索算法

6 回答

• 0

  在Java中执行该搜索的最佳方法是：

  Arrays.binarySearch(arr1, start, arr1.length, searchNum);
  

  但是，由于分配需要重新发明轮子，因此您不能只使用它 . 但是，您可以从Arrays.binarySearch获取一些提示来帮助设计您的程序 .

  您在这里遇到的主要障碍之一是您正在使用的方法签名：

  public static int arraySearch(int start, int searchNum, int [] arr1)
  

  如果您要将方法签名设置为 Arrays.binarySearch 方法使用的方法签名，则任务变得更加容易 . 所以你应该实现一些也允许指定结束索引的东西 . 我也会改变参数顺序以匹配 Arrays.binarySearch ，甚至称之为 binarySearch ：

  public static int binarySearch(int [] a, int fromIdx, int toIdx, int key)
  

  所以你应该做这样的事情 .

  public static int binarySearch(int [] a, int fromIdx, int toIdx, int key){
      if(fromIdx == toIdx) return -1;
  
      int pivotIdx = (fromIdx + toIdx)/2;
  
      if(a[pivotIdx] < key) return binarySearch(a, fromIdx, pivotIdx, key);
      if(a[pivotIdx] == key) return pivotIdx;
      if(a[pivotIdx] > key) return binarySearch(a, pivotIdx, toIdx, key);
  }
  

  回复于 2024-04-20T18:52:45+08:00
• 2

  好吧，根据你的问题，你想创建一个程序，通过二分搜索在arr1中搜索int - 好吧，为此你可以使用线性搜索和二进制搜索 .

  因为在linear search中，您可能无法获得返回值为-1，但如果您通过二进制搜索查找int值，则可以将返回值设置为-1 .

  并且用于创建子阵列的解决方案如下

  Arrays.copyOfRange(Object[] src, int from, int to)
  
  System.arraycopy(Object[] src, int srcStartIndex, Object[] dest, int dstStartIndex, int lengthOfCopiedIndices);
  

  回复于 2024-04-20T18:52:45+08:00
• 1

  我认为您正在寻找的是如下所述：

  private int BinarySearch(int[] array, int low, int high, int number)
      {
  
          // First get the middle index using high and low index 
          int medium = (high + low) / 2;
  
          // Check if the number you are looking is same as the one at middle index?
          // If that is the case, just return the middle index
          if (array[medium] == number)
          {
             return medium;
          }
          else
          {
              // if the number is not found in previous condition resume the operation. 
  
              // Check if number is greater than the middle index number 
              if (array[medium] < number)
              {
                 // call the search operation by replacing your low index with middle + 1
                 return  BinarySearch(array, medium + 1, high, number);
              }
              else
              {
                 // Here number is less than the middle index number 
                 // call the search operation by replacing your high index with middle-1 
                 return  BinarySearch(array, low, medium - 1, number);
              }
          }
      }
  

  回复于 2024-04-20T18:52:45+08:00
• 1

  因此，在递归调用中，您只需将数组的长度传递给数组的一半 . 您可以创建一个只包含数组的第一个或第二个半的新数组：http://docs.oracle.com/javase/7/docs/api/java/lang/System.html#arraycopy%28java.lang.Object,%20int,%20java.lang.Object,%20int,%20int%29

  另一个选项是使用max和min整数来标记您正在查看的数组的哪个部分 . 如果您的searchNum小于您正在查看的值，请将max设置为您的起始变量 . 如果搜索Num小于您正在查看的数字，请将min设置为start . 在您的方法开始时，如果您当前的开始是<= max或> = min返回-1，因为您将搜索之前已经查看的位置，因此您要查找的数字不在数组中 .

  回复于 2024-04-20T18:52:45+08:00
• 2

  首先回答你的问题 - 你可以使用Arrays.copyOfRange(array,from,to)创建一个子数组 .

  However, 这不是你想要做的 . 以这种方式创建子阵列是 O(n) （回想一下它是一个副本......），你不想这样做 .

  而是在您的方法中使用参数 start 和 end ，它们表示您的二进制搜索现在正在寻找的范围 .

  还要注意，当找不到元素时增加1不是二进制搜索，而是你需要设计你的算法，它总是“跳”剩余数组的一半 - 而不是一个恒定的大小 .

  根据这个，你的方法签名将是这样的：

  public static int arraySearch( int [] arr1, int start, int end, int searchNumber){ ... }
  

  然后，您将设置 mid 元素： int mid = start + (end - start)/2;
  并且您将检查所需数量是否大于 arr1[mid] .
  如果是，你将使用 arraySearch(arr1,mid+1,end,searchNumber) 递减，如果它更小，你将使用 arraySearch(arr1,start,mid,searchNumber) 递归

  希望澄清您的二进制搜索应该如何实现 .
  祝好运！

  回复于 2024-04-20T18:52:45+08:00
• 0

  试试这个：

  • 将 end 添加到@anonymous建议的方法调用中 .

  • 在每次递归调用 ArraySearch 时，将 start 和 end 的值设为
    arr1[start] < searchNum < arr1[end]

  • 并且在每次递归调用时，将 start 和 end 之间的距离（大致）设置为前一次调用的一半 .

  回复于 2024-04-20T18:52:45+08:00