Sorted Search, No Size

10.4 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.

• O(logN) time, O(N) space

• Algorithm: Find length in LogN, then preform binary search.

class Listy {
public:
    Listy() {}

    int at(int i) {
        if (i > stuff.size() - 1)
            return -1;
        else return stuff.at(i);
    }

    void push_back(int i) {
        stuff.push_back(i);
    }

private:
    vector<int> stuff;
};

int binary_search(Listy &ar, int low, int high, int target) {
    if (high < low) return INT_MIN;

    int middle = low + ((high - low) / 2);

    if (ar.at(middle) == target) return middle;
    // search right
    else if (ar.at(middle) < target) {
        binary_search(ar, middle + 1, high, target);
    }
    else {
        binary_search(ar, low, middle - 1, target);
    }

}

int binary_search_length(Listy &ar, int low, int high) {
    if (high < low) return INT_MIN;

    int middle = low + ((high - low) / 2);

    if (ar.at(middle) == -1 && ar.at(middle - 1) != -1)
        return middle;
    // search right
    else if (ar.at(middle) != -1) {
        binary_search_length(ar, middle + 1, high);
    }
    else {
        binary_search_length(ar, low, middle - 1);
    }

}

int find_max_power(Listy &ar) {
    int count = 0;
    int cur_length = pow(2, count++);

    while (ar.at(cur_length) != -1) {
        cur_length = pow(2, count++);
    }
    return count - 1;
}


int no_size_search(Listy &ar, int target) {
    if (ar.at(0) == -1) return 0;

    int max_pow = find_max_power(ar);
    int low = pow(2, max_pow - 1);
    int high = pow(2, max_pow);

    int size = binary_search_length(ar, low, high);

    return binary_search(ar, 0, size - 1, target);
}


int main() {
    Listy ar;
    for (int i = 0; i < 93893; i++) 
        ar.push_back(i);

    cout << no_size_search(ar, 239) << endl;
}