Pergunta de entrevista da empresa Bloomberg
Given a sorted array of strings which contains blank strings, write code that uses a binary search to find the location of a given string. For example, given ["apple", "", "", "ball", "", "", "", "child", "dog", ""], a search for "ball" would return 4.
Respostas da entrevista
Sigiloso
It's just modified binary search, where one has to handle a case of empty strings. The only change to BS is to skip empty strings (to the left and right) and determine where your target is; then recurse. int findPos(const vector& arr, const string& tgt, int s, int e) { if (s > e) return -1; int mid = s + (e-s)/2; // found target if (arr[mid] == tgt) return mid; // if empty if (arr[mid].empty()) { // go left int tmp = mid; while (tmp >= s && arr[tmp].empty()) --tmp; if (arr[tmp] == tgt) return tmp; else if (arr[tmp] > tgt) // tgt has to be on the left return findPos(arr, tgt, s, tmp-1); // go right tmp = mid; while (tmp tgt ? findPos(arr, tgt, s, mid-1) : findPos(arr, tgt, mid+1, e)); }