> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/divide_and_conquer/binary_search/search-in-a-big-sorted-array.md).

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