首页 > 代码库 > Binary search for the first element greater than target
Binary search for the first element greater than target
We all know how to search through an array for an element whose value equals the target value, but how to search for the element that has value greater than the target value?
A particularly elegant way of thinking about this problem is to think about doing a binary search over a transformed version of the array, where the array has been modified by applying the function
f(x) = 1 if x > target 0 else
Now, the goal is to find the very first place that this function takes on the value 1. We can do that using a binary search as follows:
int low = 0; high = numElems;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. */
Reference: http://stackoverflow.com/questions/6553970/find-the-first-element-in-an-array-that-is-greater-than-the-target
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。