#include <stdio.h>
#include <stdlib.h>
#include <execinfo.h>


// compile    gcc -rdynamic binsearcha.c to get some more meaningful stuff from output
int binarySearch(int arr[], int l, int r, int x, int rep) 
{
    printf("BSEARCH  rep:%d   low:%d  high:%d\n", rep, l, r);
    
   if (r >= l) 
   { 
        int mid = l + (r - l)/2; 
  
        // If the element is present at the middle itself 
        if (arr[mid] == x) {

	    void* callstack[128];
	    int i, frames = backtrace(callstack, 128);
	    char** strs = backtrace_symbols(callstack, frames);
	    for (i = 0; i < frames; ++i)
	    {
		printf("%s\n", strs[i]);
	    }
	    free(strs);
	    return mid;
	}
  
        // If element is smaller than mid, then it can only be present 
        // in left subarray 
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x, rep+1); 
  
        // Else the element can only be present in right subarray 
        return binarySearch(arr, mid+1, r, x, rep+1); 
   } 
  
   // We reach here when element is not present in array 
   return -1; 
}


#define SIZ 100000
int arr[SIZ];

int main(int argc, char * argv[])
{
    for (int i=0; i<SIZ; i++)
	arr[i]=i;
    int sf = (int)strtof(argv[1], NULL);
    printf("Founda %d\n", binarySearch(arr, 0, SIZ-1, sf, 0));
    //printf("Foundp %d\n", binarySearchP(arr, SIZ, sf, 0));
}

































int binarySearchP(int * arrp, int siz, int x, int rep) 
{
    printf("BSEARCH  rep:%d   siz:%d\n", rep, siz);
    
    if (siz>0)
   { 
       int *midp = (arrp + siz/2); 
        // If the element is present at the middle itself 
        if (*midp == x)  return *midp; 
  
        // If element is smaller than mid, then it can only be present 
        // in left subarray 
        if (*midp > x) return binarySearchP(arrp, siz/2, x, rep+1); 
  
        // Else the element can only be present in right subarray 
        return binarySearchP(midp+1, siz/2, x, rep+1); 
   } 
  
   // We reach here when element is not present in array 
   return -1; 
}