Binary search algorithm, with only one comparison operation

Today I want to discuss a special variation of binary search algorithm, which does only one comparison inside the loop.

The original binary search algorithm does two comparison operation inside the loop.



This algorithm is given below.

Language: C
Skill level: Beginner


/**
 * binary search algorithm implementation.
 * This search algorithm does two comparison operation within its loop.
 *
 * @param[in] array An integer array of size array_size
 * @param[in] array_size Size of the array
 * @param[in] search_key Search item
 *
 * @return if search is successful, position of the search_item else -1
 */
int binary_search(int array[], int array_size, int search_key)
{
        int low, high, mid;

        low = 0;
        high = array_size-1;

        while (low <= high) {
                mid = (low + high) / 2;
                if (search_key < array[mid])
                        high = mid - 1;
                else if (search_key > array[mid])
                        low = mid + 1;
                else
                        return mid; /* search_key found at mid */
        }
        return -1; /* search failed, search_key is not present */
}

As you can see, this algorithm does two comparison operation inside the loop. (Ignore the else case, its not comparison. Only if or else if are considered as comparison operations.)

Below is the modified version of the above algorithm, to do only one comparison operation within the loop.

/**
 * modified binary search algorithm implementation.
 * This search algorithm does only one comparison operation within its loop.
 *
 * @param[in] array An integer array of size array_size
 * @param[in] array_size Size of the array
 * @param[in] search_key Search item
 *
 * @return if search is successful, position of the search_item else -1
 */
int binary_search(int array[], int array_size, int search_key)
{
        int low, high, mid;

        low = 0;
        high = array_size;

        while (low < high) {
                mid = (low + high) / 2;
                if (search_key > array[mid])
                        low = mid + 1;
                else
                        high = mid;         /* Here array[mid] >= search_key, so we assign high = mid, instead of high = mid-1 */
        }

        /* here low == high */
        if (low < array_size && array[low] == search_key)
                return low;         /* search_key found at low */
        return -1;         /* search failed */
}

Explanation:

*pending*

Modifications:

We can do following modifications to above algorithm.

1. *pending*
   *pending*
   
2. *pending*
   *pending*

Advantages:

The advantages of this algorithm over the traditional binary search algorithm are

• *pending*
• *pending*