lets say i have an array A in non-descending order like this
A = [0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9, 10, 11, 12, 500, 600]
My question is: how to find the first occurence (index) of an element equal or greather (if 4 is not present) than 4?
O(n) solution is easy, i would like to have something faster. Probably binary search, but have no idea how to modify it.
This is a slightly modified binary search to compare with the previous element before returning. If there is a duplicate, you continue the binary search as expected, not serial search, so it's O(log(n)) independently on the structure of the sorted array (e.g. when many duplicates exist). It is written in Java.
*If the element does not present, I return the index of the next greater element, i.e. the index the key should be inserted if I had to put it in the array. I return a negative value as an indicator of "not found".
*The only exception for negative not-found value is when the key is the smallest and not-found, where you expect 0 (it doesn't have a negative). But, you can easily handle this special case to distinguish between found and not-found: e.g return the Integer.MIN_VALUE or -(array.length + 1) if -lo == 0.
*If the key is bigger than every array-value, you expect to return an index equal to array size (negative value again).
public static int indexOf(int[] a, int key) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else if (mid == 0 || key != a[mid-1]) return mid;
else hi = mid - 1; //we have a duplicate, go left
}
//not present; show index of next greater element
//OR array.length if bigger than every existing element
return -lo;
}
Standard binary search:
left limit = left end of array
right limit = right end of array
look at middle
if middle == target: stop
else:
set left or right to middle based on result of comparison
loop
This variation, changes marked with *:
left limit = left end of array
right limit = right end of array
look at middle
* if limits are close together: stop
* if middle == target and limits are not close together:
* set right to middle
* loop
else:
set left or right to middle based on result of comparison
loop
This will zero in on the leftmost incidence of target, or the point where target would go if it’s missing. Then just look around in that area to see what to return.
The following python code uses a simple binary search algorithm to find the upper value. Runtime O(log(n))
def binary_search(array, target):
lower = 0
upper = len(array)
while lower < upper:
x = lower + (upper - lower) // 2
val = array[x]
if target == val:
return x
elif target > val:
if lower == x:
break
lower = x
elif target < val:
upper = x
return upper
# Test Array
arr = [0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 5, 4, 4, 6, 7, 8]
print arr[binary_search(arr, 5)]
