Optimisation of std::binary_search of the <algorithm> header

[jay pokarna <jay dot pokarna10 at gmail dot com>]

Hey,

I am Jay.

I have written code for an optimised version of the binary_search
algorithm of the algorithm header file of the standard template
library.

I have implemented it for the integer data type, but it can be
implemented for any other data type without any changes in the
algorithm as such.

You are requested to give me feedback on my implementation.


#include<iostream>
#include<stdlib.h>
#include<math.h>
using namespace std;

bool binary_search(int arr[], int size, int ele, bool *fun_ptr);
bool binary_search(int arr[] , int size , int ele);

/*
This version of the binary_search finds an element ele in the array
arr of length size.
*/

/*
Assumptions:
1) Elements are sorted in increasing order in the array
2) The parameter size is the number of elements in the array not the
index of the last element,
i.e. the search space is arr[0,size)
3) Though , I have implemented this version with the int data type,
it is also compatible with other data types like strings , or user
defined data types.
In those cases , only the comparison operation will change without any
changes in the
algorithm.
*/

/*
  If the specified element is in the array, then the function returns
1 else returns 0.
*/

bool binary_search(int arr[] , int size , int ele)
{

/*
The element cannot be in the array if it is larger than the largest
element or smaller than the smallest element
*/

  if( ele < arr[0]||arr[size-1] < ele)
  {
    return bool(0);
  }

  /*
After this statement , the element is definitely not outside the array,
but it may or may not be in the array.
  */
  int t=sqrt(size);
  int start =0,end=t*t;

  /*
The algorithm uses the technique of square root decomposition.
It breaks down the problem (the array of length size)
to smaller problems each of length sqrt(size).
It does a kind of binary_search on the first element
of each subarray to find the subproblem to which the element belongs.
  */

  /*
The if part of the if else loop below finds which subproblem the element ele
belongs to.

The last subproblem won't be of length sqrt(size) if size is not a
perfect square.
So , as to handle this corner case , we need the else part of the loop.
  */
  if(ele < arr[end])
  {
    while(end-start>t)
    {
      int mid = (start+end)/2;

      mid -= (mid%t);

      if(arr[mid]==ele)

      {
        return bool(1);
      }
      else if(arr[mid] < ele)
      {
        start = mid;
      }
      else
      {
        end = mid;
      }
    }
  }
  else
  {
    start = end;
    end = size;
  }

  /*
After this if else loop , [start , end] will have a portion of the
array of maximum length sqrt(size)
which may contain the element.
  */

  /*
The loop below does a normal binary_search in the range [start,end]
  */
  while(end>=start)
  {
    int mid = start + ((end-start)/2);

if(ele ==arr[mid])
{
return bool(1);
}

    else if(arr[mid] < ele)
    {
      start = mid+1;
    }
    else
    {
      end = mid-1;
    }
  }
  return bool(0);
}

// Same Code as above just with a comparator specified

bool binary_search(int arr[] , int size , int ele, bool (*fun_ptr)(int ,int))
{

/*
The element cannot be in the array if it is larger than the largest
element or smaller than the smallest element
*/

  if(fun_ptr(ele,arr[0])||fun_ptr(arr[size-1],ele))
  {
    return bool(0);
  }

  /*
After this statement , the element is definitely not outside the array,
but it may or may not be in the array.
  */
  int t=sqrt(size);
  int start =0,end=t*t;

  /*
The algorithm uses the technique of square root decomposition.
It breaks down the problem (the array of length size)
to smaller problems each of length sqrt(size).
It does a kind of binary_search on the first element
of each subarray to find the subproblem to which the element belongs.
  */

  /*
The if part of the if else loop below finds which subproblem the element ele
belongs to.

The last subproblem won't be of length sqrt(size) if size is not a
perfect square.
So , as to handle this corner case , we need the else part of the loop.
  */
  if(fun_ptr(ele,arr[end]))
  {
    while(end-start>t)
    {
      int mid = (start+end)/2;

      mid -= (mid%t);

      if(!fun_ptr(arr[mid],ele)&&!fun_ptr(ele,arr[mid]))
       /*
This is equivalent to checking the condition
ele == arr[mid]
       */
      {
        return bool(1);
      }
      else if(fun_ptr(arr[mid],ele))
      {
        start = mid;
      }
      else
      {
        end = mid;
      }
    }
  }
  else
  {
    start = end;
    end = size;
  }

  /*
After this if else construct , [start , end] will have a portion of
the array of maximum length sqrt(size)
which may contain the element
  */

  /*
The loop below does a normal binary_search in the range [start,end]
  */
  while(end>=start)
  {
    int mid = start + ((end-start)/2);

if(!fun_ptr(arr[mid],ele)&&!fun_ptr(ele,arr[mid]))
       /*
This is equivalent to checking the condition
ele == arr[mid]
       */
{
return bool(1);
}

    else if(fun_ptr(arr[mid],ele))
    {
      start = mid+1;
    }
    else
    {
      end = mid-1;
    }
  }
  return bool(0);
}



Regards,
Jay Pokarna