[Sorting and Searching] interview questions #4

[rygh4775]

Sorted Search, No Size: You are given an array-like data structure Listy which lacks a size method. It does, however, have an elementAt (i) method that returns the element at index i in 0(1) time. If i is beyond the bounds of the data structure, it returns -1. (For this reason, the data structure only supports positive integers.) Given a Listy which contains sorted, positive integers, find the index at which an element x occurs. If x occurs multiple times, you may return any index.

[rygh4775]

Approach

Find length of list, then binary search.

Solution

int search(Listy listy, int x) {
    int index = 1;
    while(true) {
        int val = listy.elementAt(index);

        if(val == x) return index;  // index of x found
        if(val == -1 || val > x) break; // index of x not found

        index *= 2; // increase index
    }

    binarySearch(listy, x, index / 2, index);
}

int binarySearch(Listy listy, int x, int low, int high) {
    while(low <= hight) {
        int mid = (low + high) / 2;
        int val = listy.elementAt(mid);
        if(val > x || val == -1) {
            hight = mid;
        } else if(val < x) {
            low = mid;
        } else {
            return mid;
        }
    }
    return -1;
}

Time complexity

O(logN), N is the length of listy.

Space complexity

O(1).

[rygh4775]

int mid = (high - low) / 2 + low; // To avoid integer overflow

[rygh4775]

// To avoid infinite loop hight = mid -1; low = mid +1;