如何在排序数组上使用二进制搜索来查找特定范围内的整数数。 （有重复）

假设你有一个排序的整数数组：

{3,4,4,6,10,15,15,19,23,23,24,30} 

并且您希望找到4和23范围内的整数数。

 {4,4,6,10,15,15,19,23,23} 

因此结果将是9。

我写了一个二进制搜索实现，但我不确定如何修改它以考虑到可以有多个整数匹配范围的上限这一事实。

我想在方法签名中添加一个布尔值来询问是否要查找键的上限，但我不确定它是否可以在单个方法中完成，同时保持O（log（N））的复杂性。

或者是否有其他方法在O（log（N））时间内在排序数组中查找该范围内的项目数？

这是我到目前为止：

 int start = rangeBinarySearch(arr, 4, false); int end = rangeBinarySearch(arr, 23, true); // true would indicate that I want the position of the last occurrence of the key. int totalInRange = (Math.abs(end) - Math.abs(start) -1) private static int rangeBinarySearch(int[] items, int key, boolean lastIndex) { if(items == null) throw new IllegalArgumentException(); int start = 0; int end = items.length - 1; while(start <= end) { int mIndex = (start + end) / 2; int middle = items[mIndex]; if(middle  key) end = (mIndex -1); else return mIndex; // Possible something here to find the upper bounds? } return -(start +1); } 

Answer 1

下限和上限的范围二进制搜索是不同的 。 这里不同意味着他们有不同的停止标准和返回步骤。

1. 对于下限（左范围） ，可以调用以下函数来获取值大于或等于的排序数组中的索引，否则为-1。

    int binarySearchForLeftRange(int a[], int length, int left_range) { if (a[length-1] < left_range) return -1; int low = 0; int high = length-1; while (low<=high) { int mid = low+((high-low)/2); if(a[mid] >= left_range) high = mid-1; else //if(a[mid] 

2. 对于上限（右范围） ，可以调用以下函数来获取排序数组中的索引，其中值小于或等于它，否则为-1。

    int binarySearchForRightRange(int a[], int length, int right_range) { if (a[0] > right_range) return -1; int low = 0; int high = length-1; while (low<=high) { int mid = low+((high-low)/2); if(a[mid] > right_range) high = mid-1; else //if(a[mid] 

3. 最后 ，如果您想获得此范围内的元素数量，则可以根据上述两个函数的返回值轻松实现。

    int index_left = binarySearchForLeftRange(a, length, left_range); int index_right = binarySearchForRightRange(a, length, right_range); if (index_left==-1 || index_right==-1 || index_left>index_right) count = 0; else count = index_right-index_left+1; 

---

测试 :(有重复）

  int a[] = {3,4,4,6,10,15,15,19,23,23,24,30}; int length = sizeof(arr)/sizeof(arr[0]); int left_range = 4; int right_range = 23; int index_left = binarySearchForLeftRange(a, length, left_range); // will be 1 int index_right = binarySearchForRightRange(a, length, right_range); // will be 9 int count; // will be 9 if (index_left==-1 || index_right==-1 || index_left>index_right) count = 0; else count = index_right-index_left+1; 

---

编辑 ：当然，您可以通过传递一个额外的标志将前两个函数合并为一个，以指示它是下限或上限，但如果不是，则会更清楚。 你的选择！

Answer 2

如果您没有学习算法，请使用标准函数：

  Arrays.binarySearch 

你基本上需要首先出现你的第一个元素（4）和最后一个出现（23）和减去。 但是没有必要（4）在那里，所以阅读Arrays.binarySearch的文档，它给你在哪里（4）。

如果你期望很多（4）s，你必须编写自己的binSearch，它返回第一个和最后一个索引：

如果有前一个看i / 2，那么在索引i找到第一次出现，如果有（4）看看i /​​ 4，则查看3 * i / 4 …

Answer 3

您需要执行两次二进制搜索以查找rangeLow之前的最低索引和rangeHigh之后的highestIndex，这样您就可以计算该范围内的重复项。

当我们执行两次二进制搜索时，这将给出o（2 log n）的时间复杂度。

 private int searchArrayForNumbersInRange(int[] arr, int start, int end) { int leftIndex = searchLeft(arr, start); int rightIndex = searchRight(arr, end); int count; if (leftIndex < 0 || rightIndex < 0) return -1; if (rightIndex == leftIndex) count = 1; else { count = rightIndex - leftIndex; } return count; } private int searchLeft(int[] arr, int start) { int lo = 0; int hi = arr.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] == start && arr[mid -1] < start) { return mid - 1; } if (arr[mid] >= start) hi = mid - 1; else lo = mid + 1; } return -1; } private int searchRight(int[] arr, int end) { int lo = 0; int hi = arr.length -1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] == end && arr[mid+1] > end) return mid; if (mid <= end) lo = mid + 1; else hi = mid - 1; } return -1; }