## Saturday, March 15, 2008

### 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 */}`
• Linux kernel style coding standard is followed in this post.
• Doxygen - JavaDoc style comment blocks are used.