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
Binary search for the first element greater than target,布布扣,bubuko.com
Binary search for the first element greater than target
原文：http://www.cnblogs.com/Antech/p/3834936.html