Binary search on unknown size array

Question

Suppose an array has been given and want to find element in that array , how can you search an element in that array using binary search and that given array is already sorted and size of the array is unknown. Linear search can be applied but I am trying to figure out for faster search than linear algorithm.

Answer 1

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

Answer 2

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))

Answer 3

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.

Answer 4

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);

Answer 5

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

Answer 6

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

Answer 7

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.

Answer 8

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.