Search a sorted array for the first element larger than k 8 AnswersUse binary search algorithm since array is sorted. #!/usr/bin/env python """Search a sorted array for the first element larger than k. """ def srch(list1, srchItem): """Perform Binary search and find the first element that is larger than the arg srchItem @list1: The sorted list @srchItem: The element to be searched for finding next greater value than that """ len1 = len(list1) startIdx = 0 stopIdx = len1 - 1 stop = False # saveIdx the index of the lowest value in the sorted list saveIdx = -1 while not stop and startIdx >= 0 and stopIdx srchItem: # found greater item, but the previous one also could be greater stopIdx = midIdx - 1 saveIdx = midIdx elif list1[midIdx] srchItem: saveIdx = startIdx break elif startIdx >= len1 or stopIdx < 0: break if saveIdx == -1: return -1 # not found return list1[saveIdx] def testAll(): testList = [3, 6, 9, 34, 67] print 'Test: %s SrchItem: %d' %(testList, 34) print 'Result: %d' %srch(testList, 34) testList = [3, 6, 9, 34, 67, 69] print 'Test: %s SrchItem: %d' %(testList, 34) print 'Result: %d' %srch(testList, 34) # test for result to be the 1ast item in the list testList = [3, 6, 9, 34, 67, 69] print 'Test: %s SrchItem: %d' %(testList, 68) print 'Result: %d' %srch(testList, 68) # test for result to be the ist item in the list testList = [3, 6, 9, 34, 67, 69] print 'Test: %s SrchItem: %d' %(testList, 1) print 'Result: %d' %srch(testList, 1) # item not in the iist testList = [3, 6, 9, 34, 67, 69] print 'Test: %s SrchItem: %d' %(testList, 70) print 'Result: %d' %srch(testList, 70) if __name__ == '__main__': testAll() //Run time complexity is logn public class FirstGreatestNumberThanK { public int prepareFirstGrtst(int[] a, int k) { return firstGrtst(a, 0, a.length - 1, k); } public int firstGrtst(int[] a, int start, int end, int k) { if (end == start + 1) { if (a[start] > k) return a[start]; else return a[end]; } else { int mid = (start + end) / 2; if (k == a[mid]) return a[mid + 1]; if (k > a[mid]) { start = mid; return firstGrtst(a, start, end, k); } else { end = mid; return firstGrtst(a, start, end, k); } } } public static void main( String[] args){ FirstGreatestNumberThanK f = new FirstGreatestNumberThanK(); // int[] a = {2,4,6,8,9,12,14,16}; // even length int[] a = {2,4,6,8,9,12,14}; // odd length // System.out.println(f.prepareFirstGrtst(a, 11)); // System.out.println(f.prepareFirstGrtst(a, 3)); // System.out.println(f.prepareFirstGrtst(a, 7)); // System.out.println(f.prepareFirstGrtst(a, 15)); // execute for even length data // System.out.println(f.prepareFirstGrtst(a, 14)); // execute for even length data // System.out.println(f.prepareFirstGrtst(a, 4)); System.out.println(f.prepareFirstGrtst(a, 12)); System.out.println(f.prepareFirstGrtst(a, 2)); } } Show More Responses def find_greater(aList, item): high = len(aList) low = 0 while low < high: mid = (high + low) // 2 if item < aList[mid]: high = mid else: low = mid + 1 return aList[low] arr = [1,5,6,8,10,56] n=int(raw_input("Enter a number:")) if n in arr and arr.index(n) != len(arr)-1: print arr[arr.index(n)+1] else: print "Element not present in the list or index out or range" public int firstLargerNum(int[] sortedArr, int k){ if(sortedArr == null || sortedArr.length < 1){ throw new IllegalArgumentException("Wrong set"); } int low = 0; int high = sortedArr.length; int searchedNum = 0; while(low |