Perform binary search on a sorted array, of which you don't know the size.

Question

vkc · Accepted Answer

Seems a vague question. May be, we have to devise some strategy.

We consider range = 1 and search  for given X among those 1 nos. , if not found, we increase range = range*2,

If such right end is found , where a[range-1] > X, then we are sure that X is somewhere b/w index [0, range-1] ..... Now do simple binary search.

So, complexity = finding the apt. right end. + finding X  = log n + log n = log n

ajs · Answer

int binary_search(int value, int *array, int low, int high)
{
  if(low > high)
    return -1;

  int mid = (low+high)/2;
  if(value == array[mid])
    return mid;
  if(value  array[mid])
    return binary_search(value, array, mid+1, high);

}

int main(int argc, char *argv[])
{

  int arr[10] = {0,1,2,3,4,5,6,7,8,9};
  int i;
  for(i = -10; i < 20; i++)
    printf("%2d, find(%2d) = %2d
", i, i, binary_search(i, arr, 0, sizeof(arr)/sizeof(int)-1));
  return 0;

}

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas