simple binary search

Here is the simple version of the binary search program which I have discussed earlier.

Language: C
Skill level: Beginner

/**
 * binary search algorithm implementation.
 *
 * @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 */
}

Optional changes:

If you check above program, you will see that all our function parameters are input parameters. ie; they are not changed within the function.

so, we can make them const.

Here is the same function, with this change applied.

Language: C
Skill level: Beginner

/**
 * binary search algorithm implementation.
 *
 * @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(const int array[], const int array_size, const 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 */
}

Additional Notes:

• Linux kernel style coding standard is followed in this post.
• Doxygen - JavaDoc style comment blocks are used.