#include <iostream> #include <cassert> using namespace std; int search(string a[], int lhs, int rhs, string val) { string nil = " "; if(val == nil) return -1; while(lhs < rhs) { int mid = (lhs + rhs) >> 1; while(a[mid] == nil && mid < rhs) mid++; if(a[mid] == val) return mid; if(mid >= rhs) rhs = mid - 1; else { if(val < a[mid]) rhs = mid - 1; else lhs = mid + 1; } } return -1; } int main(void) { string a[] = { "at", " ", " ", " ", "ball", " ", " ", "car", " ", " ", "dad", " ", " " }; /* for(int i = 0; i < 13; ++i) cout << a[i] << endl;*/ cout << search(a, 0, 13, "ballcar") << endl; return 0; }