Pregunta de entrevista de Google

Given an array of integers which is circularly sorted, how do you find a given integer.

Respuesta de la entrevista

Anónimo

29 ago 2009

bool FindInCirArray (int& array_cir[SZ], int data) { int& arr[SZ] = array_cir[SZ]; enum ArDir {UNK, UP, DN}; bool pivot_found = false; ArrDir arr_dir = UNK; int pivot_point = -1; // negative means undetermined // first check if the integer is in the first three .... // determine the direction and the pivot point if (arr[1] = arr[2] >= arr[3]) { arr_dir = DN' } else { // pivot in the first 3 elements... determine by comparison ..... pivot_point = X; // value found } for (int k = 0; k data) { return (false); if (arr[k+1]) 0) { // loop to find the data and return .... } // check the end of array and return false .... return false; // end of the road... did not find data }

1