# Search in a Big Sorted Array

## Question

The array is so big so that you can not get the length of the whole array directly, and you can only access the kth number by ArrayReader.get(k). If you accessed an inaccessible index (outside of the array), ArrayReader.get will return 2,147,483,647.

## Example

```
Given [1, 3, 6, 9, 21, ...], and target = 3, return 1.
Given [1, 3, 6, 9, 21, ...], and target = 4, return -1.
```

## Analysis

Use a binary increment to find an end > target. Then find the first position of the target.

## Code

```java
public int searchBigSortedArray(ArrayReader reader, int target) {
    // use log increment to find an end first
    int index = 1;
    while (reader.get(index - 1) < target) {
        index = index * 2;
    }
    // find first pos of target
    int start = 0, mid, end = index - 1;
    while (start + 1 < end) {
        mid = start + (end - start) / 2;
        if (reader.get(mid) == target) {
            end = mid;
        } else if (reader.get(mid) < target) {
            // median < target, search right section
            start = mid + 1;
        } else {
            // median > target, search left section
            end = mid - 1;
        }
    }
    if (reader.get(start) == target) {
        return start;
    } else if (reader.get(end) == target) {
        return end;
    } else {
        return -1;
    }
}
```


---

# Agent Instructions: 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:

```
GET https://zedive.gitbook.io/project-l/part-2/divide_and_conquer/binary_search/search-in-a-big-sorted-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
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.