If you can test whether you have fallen out of the array range, then you could use a modified binary search (assume 1-based array):

1. lower = 1, upper = 1;
2. while (A[upper] < element) upper *= 2;
3. Normal binary search on (lower, upper).

Otherwise, there is no real way to do it: assume you find something somewhere that equals to the element you need, you cannot know if it already falls out of the array.

Assuming the array A is sorted (otherwise you can't do binary search), and the element you're searching for is k, you can find an index i such that k < A[i], and then do binary search from 1 to i (1-indexed array). This is because once k < A[i], k is guaranteed to be found (or not found) in the range of sorted elements A[1..i].

To find the index i, you would start at i = 1, then double it if k > A[i]. This is like binary search except you're doubling the search range, so it will still have a O(log n) running time.

The algorithm is something like: Set i = 1, then repeat until k <= A[i]:

• if k > A[i] then let i = i*2

If k == A[i], then you're done, otherwise do binary search as usual on A[1..i].

Here's a start:

I might try something like this (in Java-esqe language). (Assumes an integer array)

int endOfArray = 10;
try {
   while (true) {
     int value = theArray[endOfArray*2];
     if (value > requestedValue)  // good enough 
        return doBinarySearch(theArray, 0, endOfArray, requestedValue);
     else
       endOfArray*=2;
   }
}

catch (ArrayIndexOutOfBoundsException aioob) {
  // we know that the end of the array is less than endOfArray*2 but > endOfArray
  // do something clever here TBD.   :-)
}

Note added later: If the array is "C-like" and has 0s at the end, you'd also have to check for that. BTW, if anybody has a simple solve for the "something clever here" part, please feel free to edit the answer.

This one is working for me, This is O(log N + log N) i.e still O(log N)? This one is fitting the sub-array also in an efficient manner. O(log N)

static int bSearch (int needle, int[] arr)
    {
    boolean done = false;
    int i = 1;
    int lower = 0;
    int upper = 1;
    int temp;
    while (!done)
    {
        try{
            if (needle == arr[upper]) 
                return upper;
            else if (needle > arr[upper])
            {
                temp = lower;
                lower = upper;
                upper = temp + (int) Math.pow(2,i);
                i = i + 1;
            }
            else
            {
                done = true;
                break; //found the upper bounds
            }
        }
        catch (IndexOutOfBoundsException e)
        {
        upper = (upper -lower) / 2;
            i = 0;
        }
    }
    if (done == true)
        //do normal binary search with bounds lower and upper and length upper-lower
    else
        return -1;
    }

The following should work (haven't tested), but should have the same bounds as binary search, O(log(n)):

private bool hasValue(int[] array, int search, int start, int end)
{
    int mid = (start+end)/2;

    try
    {
        //Check to see if we can grab the value
        int value = array[mid];

        //If we are here, we are in the array

        //Perform the binary search
        if (value==search)
            return true;
        else if (end <= start)
            return false;
        else if (value>search)
            return hasValue(array, search, start, mid);
        else
            return hasValue(array, search, mid, end*2);

    }
    catch(ArrayIndexOutOfBoundsException e)
    {
        //If we are here, then we were outside the array, so 
        //loop through the lower half
        return hasValue(array, search, start, mid);
    }


}

public bool hasValue(int[] array, int search)
{
    // 0 is the start of the array (known)
    // 1 is the end--start with any number that is greater than max(start, 1)
    return hasValue(array, search, 0, 1);
}

Here's an example usage

// 2 is the value you are looking for
bool hasTwo = hasValue(array, 2);

import java.util.Scanner;

public class SolutionB {
    int size;
    int arr[];
    int M;
    void inputData(){
        Scanner in = new Scanner(System.in);
        size = in.nextInt();
        M = in.nextInt();
        arr = new int[size + 1];
        for(int i = 1; i <= size; i+=1){
            arr[i] = in.nextInt();
        }
    }

    void findMIndex(){
        int start = 1;
        int end = 2;
        int j = 0;
        int flag = 0, flag2=0;

         for (int i = 2; flag == 0; ) {
             try{
                 if (arr[end] > M) {
                     flag = 1;
                 }
                 else if (arr[end] == M) {
                     System.out.println(end);
                     return;
                 }
                 else if(start == end) {
                     flag=1;
                     flag2=1;
                 }
                 else {
                     i *= 2;
                     start = end;
                     end = i;
                 }
             }
             catch (ArrayIndexOutOfBoundsException e){
                 end = start + (end - start)/2;
             }
         }
         if(flag2==0)
         {

             binary(start, end);
         }
         else
         {
             System.out.println("NOT_FOUND");
             return;
         }
    }

    void binary(int start, int end){
        int index = -1;
        while( start <= end ){
            int mid =  (start + ( end - 1 )) / 2 + 1;
            if( M == arr[mid] ){
                index = mid;
                break;
            }
            else if(M < arr[mid]){
                end = mid - 1;
            }
            else {
                start = mid + 1;
            }
        }
        if( index == -1 ){
            System.out.println("NOT_FOUND");
        }
        else{
            System.out.println(index);
        }
    }

    public static void main(String[] as){
        SolutionB obj = new SolutionB();
        obj.inputData();
        obj.findMIndex();
    }

}

This solution is for a 1-indexed array. It works for me.

Python Solution: This approach would work if the element is present in the array

def searchArray(nums, element):
    if nums[0] == element: return 0
    i = 1
    base = 0
    done = False
    while not done:
        try:
            if nums[base + i] == element:
                print('if')
                return base + i
            elif nums[i] < element:
                print('elif')
                i = i * 2
            else:
                print('else')
                done = True
                print('base, i', base, i)
                base = base + i//2
                i = 1
        except:
            print('out of bound base, i', base, i)
            base = base + i//2
            i = 1
            
nums = [2, 3, 5, 6, 8, 9, 10, 11]
print(searchArray(nums, 11))

First find the array size using binary search, then apply binary search on the array:

import sys


def find_arr_size(arr):  # O(log(sys.maxsize))
    b = 1
    e = sys.maxsize
    size = 1
    while b <= e:
        m = (e + b) // 2
        try:
            arr[m]
            size = m + 1
            b = m + 1
        except:
            e = m - 1
    return size


def find_x_ind(arr, size, x):  # O(log(arr_size))
    b = 0
    e = size - 1
    while b <= e:
        m = (b + e) // 2
        if arr[m] == x:
            return m
        if arr[m] < x:
            b = m + 1
        else:
            e = m - 1
    return -1


def search(arr,x):
    if not arr:
        return -1
    size = find_arr_size(arr)
    ind = find_x_ind(arr,size,x)
    return ind


arr = [1,2,2,3,3,4]
assert search(arr,3) in [3,4]
assert search(arr,5) == -1