© 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