• 0

Find smallest number greater than a given integer in an array
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (12243)

Suppose you are given a sorted integer array and an integer that may or may not be present in the array. How will you find the smallest number in the array that is greater than the given integer?


Posted Answers

  • Posted: 7 years ago
  • 0 0
  • Edit

We can use a modified binary search.


  • If the middle element of the array is greater than or equal to the given integer AND the element before the middle element of the array is less than the given integer, return the middle element of the array.
  • If the middle element of the array AND the element before it are both greater than the given integer, recurse the algorithm on the first half of the array.
  • Else, recurse the algorithm on the second half of the array.

Running time = \( O(logn) \).

public int findSmallestIntGreaterThnGiven(int[] array, int start, int end, int k){

      int middle = array.length/2;

      if(array[middle] >= k  & &  array[middle-1]  <  k)
          return array[middle];
      elseif(array[middle] > k  & &  array[middle-1] > k)
          return findSmallestIntGreaterThnGiven(array, start, middle, k);
      else
          return findSmallestIntGreaterThnGiven(array, middle, end, k);
  }
You need to Sign In to post your solution.