CareerCup

// infA[] - infinite array with '$' as a terminating character
bool binary_search(char *infA, char x) {

    int l = 0, r = 1;
    while(1) { // first phase: find the array bounds
        char a = infA[r - 1];
        // here we either found the valid range or hit the end of the data:
        // in any case we can reduce the search space to [l; r]
        if(a == '$' || x < a) { 
            break;
        }
        if(x == a) // found the actual val
            return true;  
        // otherwise we keep on moving the right boundary
        l = r - 1, r = r * 2;
    }
    printf("'x' can only lie between [%c; %c]\n", infA[l], infA[r]);

    // second phase: run an ordinary binary search with account for
    // the terminating symbol '$'
    while(1) {
        int mid = (l + r) / 2;
        char a = infA[mid];
        if(a == '$' || x < a) {
            r = mid;
        } else if(x > a) {
            l = mid + 1;
        } else  // gotcha !!
           return true;
        if(l == r)
            return false; // not found
    }
}

<pre lang="" line="1" title="CodeMonkey73858" class="run-this">#include <iostream>
using namespace std;

#include <string.h>

int bs(char* p, int l, int r, char c)
{
while (l <= r)
{
int mid = (l + r)/2;
char m = *(p + mid);

if (m == c)
{
return mid;
}

if (m == '$')
{
int cur = mid + 1;
while (cur <= r && *(p + cur) == '$')
{
++cur;
}
if (cur <= r)
{
l = cur;
}
else
{
r = mid - 1;
}

continue;
}

if (m <= c)
{
l = mid + 1;
continue;
}

if (m > c)
{
r = mid - 1;
continue;
}

}

return -1;
}

int main()
{
char* p = "$$$$$$$0123456999$$$$$$$$$$$$$$$$$$$$$$";
int l = 0;
int r = strlen(p) - 1;

for (char i = '0'; i <= '9'; ++i)
cout << i << " " << bs(p, l, r, i) << endl;
}
</pre><pre title="CodeMonkey73858" input="yes">
</pre>

<pre lang="" line="1" title="CodeMonkey65418" class="run-this">#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define $ 9999999
using namespace std;
int main(){
int a[]={1,2,3,4,5,6,7,9,15,23,29,34,37,52,59,63,64,68,75,99,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,};
int element;
cin>>element;
int low=0;
int high=1,mid;
while(1){
mid=(low+high)/2;
if(element==a[mid]){
cout<<mid;
break;
}
if(a[low]=='$' || low>=high){
cout<<"Not Found"<<endl;
break;
}
if(a[low]!='$' && a[mid]=='$'){
high = mid-1;
continue;
}
if(a[high]=='$'){
if(element>a[mid])
low=mid+1;
else
high=mid-1;
}
else if(a[high]!='$'){
if(element > a[high]){
low=high;
high=2*high;
}else{
if(element>a[mid])
low=mid+1;
else
high=mid-1;
}
}
}
} </pre><pre title="CodeMonkey65418" input="yes">
</pre>

dude.. explain the logic

modified binary search.
initially, let low = 0 and hi = 2,
let k = number to find.

while( a[hi] != '$' )
    if  k  == a[hi] return hi
    if  k <  a[hi] do a binary search 
    else  
         low = hi 
         hi = 2*hi

return -1 at end ( number not present )