# Search in unknown size array

Given an integer dictionary A of unknown size, where the numbers in the dictionary are sorted in ascending order, determine if a given target integer T is in the dictionary. Return the index of T in A, return -1 if T is not in A.

**Assumptions**

* dictionary A is not null
* dictionary.get(i) will return null(Java)/INT\_MIN(C++)/None(Python) if index i is out of bounds

**Examples**

* A = {1, 2, 5, 9, ......}, T = 5, return 2
* A = {1, 2, 5, 9, 12, ......}, T = 7, return -1

**Key Insight:**

First, identify the frame to search. Then perform the binary search.

```java
public class Solution {
  public int search(Dictionary dict, int target) {
    if (dict == null) return -1;
    if (dict.get(1) == null){
      return dict.get(0) == target ? 0 : -1;
    }
    int left = 0;
    int right = 1;
    //double right until we know target is within range of left->right
    while(dict.get(right) != null && dict.get(right) < target){
      left = right;
      right = 2 * right;
    }
    return binarySearch(dict, target, left, right);
  }

  private int binarySearch(Dictionary dict, int target, int left, int right){
    while(left <= right){
      int mid = left + (right - left) / 2;
      if (dict.get(mid) == null || dict.get(mid) > target){
        right = mid - 1;
      } else if (dict.get(mid) < target){
        left = mid + 1;
      } else {
        return mid;
      }
    }
    return -1;
  }
}
```

**TC:** O(log(N))

**SC:** O(1)