Search a sorted array for the first element larger than k

Question

Bharati Desai · Accepted Answer

#!/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()

Sruthi · Answer

//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));
		
	}
}

ronak · Answer

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]

Anoniem · Answer

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"

Gokhan · Answer

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

Anoniem · Answer

Use binary search algorithm since array is sorted.

LinkedIn

Sollicitatievraag bij LinkedIn

Antwoorden op sollicitatievragen

Gevolgde bedrijven

Vacatures