# Find the first element larger than k in a sorted array

Question 41. Find the first element larger than k in a sorted array

Consider the sorted array A = {10, 20, 20, 30, 40, 50}. The first element larger than 25 is 30. In normal binary search, we search for a particular element and stop when we find the element. When we are trying to find the first element larger than k, k may not even exist in the array. So we instead use a modified form of binary search where we keep track of the first element larger than k as we search the array. The time complexity is O(logn). The code is given below

## C/C++

```
/*
a: sorted array containing elements in non-decreasing order
length: number of elements in the array
k: we are searching for the number immediately above k
Returns: the number immediately greater than k in the array if it exists,
MAX_INT otherwise
*/
int find_next_higher(int a[], int length, int k)
{
int low, high, mid, result;

low = 0;
high = length - 1;

result = MAX_INT;
while (low <= high) {
mid = (low + high) / 2;

if (a[mid] > k) {
result = a[mid]; /*update the result and continue*/
high = mid - 1;
} else {
low = mid + 1;
}
}

return result;
}

```

## Java

```
/*
a: sorted array containing elements in non-decreasing order
k: we are searching for the number immediately above k
Returns: the number immediately greater than k in the array if it exists,
MAX_INT otherwise
*/
public static int findNextHigher(int[] a, int k) {
int low = 0;
int high = a.length - 1;

int result = MAX_INT;
while (low <= high) {
int mid = (low + high) / 2;

if (a[mid] > k) {
result = a[mid]; /*update the result and continue*/
high = mid - 1;
} else {
low = mid + 1;
}
}

return result;
}

```

## Python

```
#a: sorted list containing elements in non-decreasing order
#k: we are searching for the number immediately above k
#Returns: the number immediately greater than k in the list if it exists,
#		MAX_INT otherwise
def find_next_higher(a, k) :
low = 0
high = len(a) - 1

result = MAX_INT
while (low <= high) :
mid = (low + high) // 2

if (a[mid] > k) :
result = a[mid] #update the result and continue
high = mid - 1
else :
low = mid + 1

return result

```