sorting.h File Reference

prototypes for sorting.h More...

Go to the source code of this file.

Functions
int	binary_search (int *poffset, int target, int *sorted_integers, int num_integers)
template<typename doubletype >
int	binary_search (int *poffset, doubletype target, doubletype *list, int length)

Detailed Description

prototypes for sorting.h

Definition in file sorting.h.

Function Documentation

binary_search() [1/2]

int binary_search	(	int *	poffset,
		int	target,
		int *	sorted_integers,
		int	num_integers
	)

Definition at line 14 of file binary_search.cpp.

                                                                                { /*{{{*/
 
   /*output: */
   int offset=0;  //offset, if found
   int found=0;   //found=0 if target is not found, 1 otherwise.
 
   /*intermediary: */
   int *beg = NULL;
   int *end = NULL;
   int *mid = NULL;
 
   _assert_(sorted_integers);
 
   // point to beginning and end of the array
   beg=sorted_integers;
   end=sorted_integers+num_integers;
   mid=beg+(int)(num_integers/2);
 
   if (*beg==target){
      found=1;
      offset=0;
   }
   else if(*(end-1)==target){
      found=1;
      offset=num_integers-1;
   }
   else{
      while((beg <= end) && (*mid != target)){
         // is the target in lower or upper half?
         if (target < *mid) {
            end = mid - 1;  //new end
            mid = beg + (end-beg)/2;  //new middle
         }
         else {
            beg = mid + 1;  //new beginning
            mid = beg + (end-beg)/2;  //new middle
         }
      }
 
      //did we find the target?
      if (*mid == target) {
         found=1;
         offset=mid-sorted_integers;
      }
      else {
         found=0;
      }
   }
 
   /*Assign output pointers:*/
   *poffset=offset;
 
   /*Return result: */
   return found;
} /*}}}*/

binary_search() [2/2]

template<typename doubletype >

int binary_search	(	int *	poffset,
		doubletype	target,
		doubletype *	list,
		int	length
	)

Definition at line 9 of file sorting.h.

                                                                                                            { /*{{{*/
   /*
    *             l[0]  l[1]  l[2]        l[n]  l[n+1]   l[length-1]
    *     <-------+-----+-----+-----+ ... +-----+........+-------------->
    * offset: -1     0     1     2           n              length -1
    *  
    *  offset = -1        target < list[0]
    *  offset = n         list[n] <= target < list[n+1]
    *  offset = length-1  list[length-1] <= target
    */
 
   /*output: */
   int offset = 0;
   int found  = 0;
 
   /*intermediary: */
   int n0 = 0;
   int n1 = int(length/2);
   int n2 = length-1;
 
   if(target<list[n0]){
      found  = 1;
      offset = -1;
   }
   else if(target>=list[n2]){
      found  = 1;
      offset = length-1;
   }
   else{
      for(;;){
         /*did we find the target?*/
         if(list[n1]<=target && list[n1+1]>target){
            found  = 1;
            offset = n1;
            break;
         }
         else if(target < list[n1]){
            n2 = n1;
            n1 = n0 + int((n2-n0)/2);
         }
         else{
            n0 = n1;
            n1 = n0 + int((n2-n0)/2);
         }
      }
   }
 
   /*Assign output pointer and return*/
   *poffset=offset;
   return found;
} /*}}}*/