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