/**
 * Binary search done recursively.
 * The real point here is the break to show the stack frame when teh item is found
 * @author gtowell
 * @Created: Sep 2019
 * Modified: March 2021
 * // compile  gcc -rdynamic binsearch.c to get some more meaningful stuff from output
 * **/

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

#pragma GCC diagnostic error "-Wframe-larger-than=1"

#ifndef NULL
#define NULL (void *) 0
#endif

/**
 * Do binary search recursively on the passed in array
 * @param arr -- the array to search
 * @param l -- the lowest index still being considered
 * @param h -- the highest index still being considered
 * @param x -- the thing being searched for
 * @param rep -- the depth of teh search (not really needed but amusing to track)
 * @return the location of x in the array, or -1 if not
 * **/
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));
}

































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; 
}