在排序数组 (Java) 中查找整数出现范围的问题

Question

我正在尝试在 sorted 数组中查找键的边界。例如，该函数接受一个数组和一个键，并且 return 根据数组的内容和给定的键设置下限和上限（例如 public static int [] boundFinder）。

下限是键出现的最低索引，上限是键出现的最高索引。这是具有正确输出的示例输入：

排序数组：{ 2, 3, 4, 5, 5, 5, 5, 5, 9, 9, 14, 40 }

键：5

输出：3、7

在我的代码中，我使用二进制搜索，因为数组已排序。但是，我很容易获得上限，但在获得下限方面一直存在问题。我知道我可以修改我的二进制搜索方法，但我尝试使用 Java 的数学库来为我的边界获取正确的最小值和最大值。我还将我的结果存储到一个数组中 return 返回给用户。

如果我的方法可以改进（代码如下），请告诉我。我想知道我是否可以使用不同的数据结构或算法以最佳速度解决这个问题？我知道我总是可以遍历整个数组，但这不是最好的。

提前致谢！

public static int[] boundFinder(int[] array, int key) {
    int [] resultArr = new int[2];

    int floorIndex = -1;
    int ceilingIndex = array.length;

    while (floorIndex + 1 < ceilingIndex) {
        resultArr[0] = Math.min(resultArr[0], binarySearch(array, floorIndex, ceilingIndex, key));
        resultArr[1] = Math.max(resultArr[1], binarySearch(array, floorIndex, ceilingIndex, key));
        floorIndex++;
    }

    return resultArr;
}

public static int binarySearch(int[] array, int floorIndex, int ceilingIndex, int key) {
    while (floorIndex + 1 < ceilingIndex) {
        int distance = ceilingIndex - floorIndex;
        int halfDistance = distance/2;
        int guessIndex = floorIndex + halfDistance;

        int guessValue = array[guessIndex];

        if (guessValue == key) {
            return guessIndex;
        } else if (guessValue > key) {
            ceilingIndex = guessIndex;
        } else {
            floorIndex = ceilingIndex;
        }
    }
    return 0;
}

Answer 1

我会告诉你一个点击我的方法：

int min=-1; int max=0;
public int[] boundFinder(int[] array,int key)
{
    int[] resultArray=new int[2];
    for(int i=0;i<array.length;i++)
{
   if(array[i]==key)
{
     max=i;
     if(min==-1)//so that only lower bound is assigned to min.
     {
         min=i;
      }
}
}
 resultArray[0]=min;  //stores the bounds
 resultArray[1]=max;
 return resultArray;
}

min 的值将仅更改一次，因为我们使用 if statement.But max 将具有最终或最高界限 value.Finally, 我已将这些值存储在数组中 (resultArray) 并 return 对其进行编辑。

如果你想让它更简单，你可以尝试使用 array list 它有一些预定义的函数来 return 索引。

Answer 2

您的逻辑适用于上（右）界，因为您不断增加数组的下起始索引，并且当您到达存在元素的元素的最后一个索引时，二进制搜索将找到该元素并return.

相同的逻辑不适用于下（左）界，因为您 return 在找到元素后立即。一旦到达元素所在的最后一个索引，它将始终 return 0 并且这就是发生的情况。

您的方法的主要缺点是 binarysearch 方法调用的数量等于数组中元素的数量。所以算法的复杂度变成O(n log (n))。这比 O(n) 更糟糕，后者可以通过简单的线性搜索来实现。

您需要编写两个单独的实现来获取数组中元素的 left most 和 right most 索引。

因为一旦找到数组中的元素，就需要向右或向左移动以找到元素的边界索引。进入任一端边界的逻辑与其他不同。

找到元素后，检查索引的左侧，如果也等于键，则再次调用搜索。

public static int leftSearch(int a[], int key, int l, int h) {
  if (l<=h) {
    int mid = (l+h)/2;
    if (a[mid] == key) {
      if (mid > 0 && a[mid-1] == key) {
        return leftSearch(a, key, l, mid-1);
      } else {
        return mid;
      }
    }
    if (a[mid] > key) {
      return leftSearch(a, key, l, mid-1);
    } else {
      return leftSearch(a, key, mid+1, h);
    }
  }
  return -1;
}

找到元素后，检查索引的右侧，如果也相等，则再次调用搜索。

public static int rightSearch(int a[], int key, int l, int h) {
  if (l<=h) {
    int mid = (l+h)/2;
    if (a[mid] == key) {
      if (mid<h && a[mid+1] == key) {
        return rightSearch(a, key, mid + 1, h);
      } else {
        return mid;
      }
    }
    if (a[mid] > key) {
      return rightSearch(a, key, l, mid-1);
    } else {
      return rightSearch(a, key, mid+1, h);
    }
  }
  return -1;
}

主要方法：

public static void main(String[] args) {
  int array[] = new int[]{ 2, 3, 4, 5, 5, 5, 5, 5, 9, 9, 14, 40 };
  int leftIndex = leftSearch(array, 5, 0, array.length-1);
  System.out.println(leftIndex);
  int rightIndex = rightSearch(array, 5, 0, array.length-1);
  System.out.println(rightIndex);
}

输出：

3
7

Answer 3

您可以按如下方式自定义您的二进制搜索来实现您的要求...

public static void main(String[] args){
        int[] array = { 2, 3, 4, 5, 5, 5, 5, 5, 9, 9, 14, 40 };
        //int[] array = { 1, 2, 5, 6, 6, 6, 6, 6, 6, 6, 6, 10 };
        int key = 5; 

        int len = array.length;

        int [] resultArr = new int[2];
        resultArr[0]=0;
        resultArr[1]=len-1;


        while(!(array[resultArr[0]]==key && array[resultArr[1]]==key)){
            int mid = (resultArr[0]+resultArr[1])/2;
            if(array[mid]>key){
                    resultArr[1] = mid-1;
            }
            else if (array[mid]<key){
                    resultArr[0]=mid+1;
            }
            else{
                if(array[resultArr[1]]!=key){
                    resultArr[1]=resultArr[1]-1;
                }
               else if (array[resultArr[0]]!=key)
                    resultArr[0]=resultArr[0]+1;
            }
        }

        System.out.println("LowerBoundary - "+resultArr[0]+" UpperBoundary - "+resultArr[1]);

    }

Answer 4

不要使用两个单独的二分搜索实现，而是使用一个总能找到最左边匹配项的二分搜索实现。使用 key 调用一次以查找第一次出现的位置，然后使用 key+1 第二次调用它以查找数字 after [=12] 的第一次出现=].您想从第二次调用返回的结果中减去 1。

因此您的 boundFinder 方法会执行此操作（假设您使用的是 Java 的内置 binarySearch 方法）：

int min = binarySearch(array, key);
int max = binarySearch(array, key+1) - 1;

这假设 key 和 key+1 都在数组中。如果你不能假设 key+1 在数组中，那么你会写：

int max;
int next = binarySearch(array, key+1);
if (next < 0)
{
    max = -key - 1;
}
else
{
    max = key-1;
}
// fill your result array with min and max

在排序数组 (Java) 中查找整数出现范围的问题

Issue with finding the bounds of integer occurrence in a sorted array (Java)

java

arrays

sorting

binary-search

data-structures