Find the first element larger than k in a sorted array

© Parineeth M R

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