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.

Psychologize

The title is not implied in the question body. Don't you know the array size? – Suttle

sorry for that i have edited the question.. – Psychologize

"array of unknown size" = array with a special end-of-array value? If so, you are practically force to read it in linear order... so I don't see how you'd implement other thing – Suttle

By unknown you mean "arbitrary" known size, right? – Insufficiency

@Suttle and @ acdcjunior Unknown means where the number of data is not known. – Psychologize

@MrA no sarcasm needed. "unknown" might mean unknown at the moment of algorithm coding or unknown at the moment of algorithm calling. If you really mean the later, then I restate my comment above. – Suttle

And your language doesn't have a call to return the size of an array at runtime? Strange. I have never seen a language which allows array sizes to be set at run time but does not allow array sizes to be read at run time. – Darice

@Peter Web I know it sounds strange..Basically this question was asked in one of my interview and I had same reaction and found it really challenging..Since then I am trying to figure it out. – Psychologize

Answer 1

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.

Sharie

why we are multiplying upper by 2 only?? can we some oter value instead of 2 – Sleet

In step2, we can update lower value to the previous upper value. This limits the range for binary search in step 3. – Caulk

Answer 2

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

Stope

Answer 3

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.

Normy

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

Wie

When would this return false? – Ardellaardelle

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

Psychomotor

Answer 6

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.

Syrian

Answer 7

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

Standard

Answer 8

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

Supraorbital