> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/interview_questions_4/sorted-search-no-size.md).

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

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/interview_questions_4/sorted-search-no-size.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.