查找大于目标的sorting数组中的第一个元素

在一般的二分search中，我们正在寻找出现在数组中的值。 然而有时候，我们需要find第一个大于或小于目标的元素。

这是我的丑陋，不完整的解决scheme：

// Assume all elements are positive, ie, greater than zero int bs (int[] a, int t) { int s = 0, e = a.length; int firstlarge = 1 << 30; int firstlargeindex = -1; while (s < e) { int m = (s + e) / 2; if (a[m] > t) { // how can I know a[m] is the first larger than if(a[m] < firstlarge) { firstlarge = a[m]; firstlargeindex = m; } e = m - 1; } else if (a[m] < /* something */) { // go to the right part // how can i know is the first less than } } } 

这种问题有没有更优雅的解决scheme？

Answer 1

考虑这个问题的一个特别优雅的方法是考虑在数组的已转换版本上进行二分search，其中数组已经通过应用函数

 f(x) = 1 if x > target 0 else 

现在，我们的目标是find这个函数取值1的第一个位置。我们可以使用二分search来做到这一点，如下所示：

 int low = 0, high = numElems; // numElems is the size of the array ie arr.size() while (low != high) { int mid = (low + high) / 2; // Or a fancy way to avoid int overflow if (arr[mid] <= target) { /* This index, and everything below it, must not be the first element * greater than what we're looking for because this element is no greater * than the element. */ low = mid + 1; } else { /* This element is at least as large as the element, so anything after it can't * be the first element that's at least as large. */ high = mid; } } /* Now, low and high both point to the element in question. */ 

要看到这个algorithm是正确的，考虑每一个比较。 如果我们发现一个元素不大于目标元素，那么它和它下面的所有元素都不可能匹配，所以不需要search那个区域。 我们可以recursion地search右半部分。 如果我们发现一个比所讨论的元素大的元素，那么它之后的任何元素都必须更大，所以它们不能成为更大的第一个元素，所以我们不需要search它们。 中间元素因此是最后的可能的地方。

请注意，在每次迭代中，我们至less会放弃一半剩余的元素。 如果最高分支执行，那么[low，（low + high）/ 2]范围内的元素全部被丢弃，导致我们丢失floor（（低+高）/ 2） – low + 1> =（low +高）/ 2 – 低=（高 – 低）/ 2个元素。

如果执行底部分支，则范围[（低+高）/ 2 + 1，高]中的元素全部被丢弃。 这使我们失去了高层（低+高）/ 2 + 1> =高（低+高）/ 2 =（高 – 低）/ 2元素。

因此，我们最终将在这个过程的O（lg n）迭代中find比目标更大的第一个元素。

编辑：这是数组上运行的algorithm的跟踪0 0 1 1 1 1。

最初，我们有

 0 0 1 1 1 1 L = 0 H = 6 

所以我们计算mid =（0 + 6）/ 2 = 3，所以我们检查位置3的元素，其值为1.由于1> 0，我们设置high = mid = 3。

 0 0 1 LH 

我们计算mid =（0 + 3）/ 2 = 1，所以我们检查元素1.由于这个值为0 <= 0，所以我们设置mid = low + 1 = 2.现在我们剩下L = 2和H = 3：

 0 0 1 LH 

现在，我们计算mid =（2 + 3）/ 2 = 2。在索引2处的元素是1，并且由于1≥0，我们设置H = mid = 2，在这一点上，我们停止，实际上我们正在寻找在大于0的第一个元素。

希望这可以帮助！

Answer 2

如果数组sorting（假设n是数组a[]的大小），则可以使用std::upper_bound ：

 int* p = std::upper_bound( a, a + n, x ); if( p == a + n ) std::cout << "No element greater"; else std::cout << "The first element greater is " << *p << " at position " << p - a; 

Answer 3

下面的recursion方法如何：

  public static int minElementGreaterThanOrEqualToKey(int A[], int key, int imin, int imax) { // Return -1 if the maximum value is less than the minimum or if the key // is great than the maximum if (imax < imin || key > A[imax]) return -1; // Return the first element of the array if that element is greater than // or equal to the key. if (key < A[imin]) return imin; // When the minimum and maximum values become equal, we have located the element. if (imax == imin) return imax; else { // calculate midpoint to cut set in half, avoiding integer overflow int imid = imin + ((imax - imin) / 2); // if key is in upper subset, then recursively search in that subset if (A[imid] < key) return minElementGreaterThanOrEqualToKey(A, key, imid + 1, imax); // if key is in lower subset, then recursively search in that subset else return minElementGreaterThanOrEqualToKey(A, key, imin, imid); } } 

Answer 4

我下面的实现使用条件bottom <= top这是不同于@templatetypedef的答案。

 int FirstElementGreaterThan(int n, const vector<int>& values) { int B = 0, T = values.size() - 1, M = 0; while (B <= T) { // B strictly increases, T strictly decreases M = B + (T - B) / 2; if (values[M] <= n) { // all values at or before M are not the target B = M + 1; } else { T = M - 1;// search for other elements before M } } return T + 1; } 

Answer 5

这里是一个在JAVA中修改的二进制search代码，其时间复杂度为O（logn） ：

• 如果元素存在，则返回要被search的元素的索引
• 如果search到的元素不在数组中，则返回下一个大元素的索引
• 如果search到大于数组最大元素的元素，则返回-1

 public static int search(int arr[],int key) { int low=0,high=arr.length,mid=-1; boolean flag=false; while(low<high) { mid=(low+high)/2; if(arr[mid]==key) { flag=true; break; } else if(arr[mid]<key) { low=mid+1; } else { high=mid; } } if(flag) { return mid; } else { if(low>=arr.length) return -1; else return low; //high will give next smaller } } public static void main(String args[]) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); //int n=Integer.parseInt(br.readLine()); int arr[]={12,15,54,221,712}; int key=71; System.out.println(search(arr,key)); br.close(); }