Return to Revisions

Update bin_search with a best-case scenario(O(1)) if the array has only 1 element.

int bin_search (int arr[], int min_index, int max_index, int element)
{
    // this is the best case scenario
     if(min_index == max_index)
     {
         if(arr[min_index] == element) 
            return min_index;
         else 
            return -1;
     }
     if (min_index > max_index)
     {
            return -1;
     }
     else
     {      
             int mid_index = (min_index + max_index) / 2;
             if (arr[mid_index] > element)
             {
                    return bin_search(arr, min_index, mid_index - 1, element);
             }
             else if (arr[mid_index] < element)
             {
                    return bin_search(arr, mid_index + 1, max_index, element);
             }
             else
             { 
                    return mid_index;
             }
    }
}

UPDATE 1

There is also an iterative process.

int bin_search (const int arr[], int min, int max, int element)
{
     int high = max+1;
     int low = min;
     while(low < (high-1))
     {
         int mid = (low + high)/2;
         if(element < arr[mid])
            high = mid;
         else
            low = mid;
     }
     if(arr[low] == element)
        return low;
     else
        return 1; // not found
}