binary_search.c File Reference

Program to perform binary search of a target value in a given sorted array. More...

#include <assert.h>
#include <stdio.h>

Include dependency graph for binary_search.c:

Functions
int	binarysearch1 (const int *arr, int l, int r, int x)
	Recursive implementation. More...
int	binarysearch2 (const int *arr, int l, int r, int x)
	Iterative implementation. More...
void	test ()
	Test implementations.
int	main (void)
	Main function.

Detailed Description

Program to perform binary search of a target value in a given sorted array.

Authors

James McDermott - recursive algorithm

Krishna Vedala - iterative algorithm

Function Documentation

binarysearch1()

int binarysearch1	(	const int *	arr,
		int	l,
		int	r,
		int	x
	)

Recursive implementation.

Parameters

[in]	arr	array to search
	l	left index of search range
	r	right index of search range
	x	target value to search for

Returns

location of x assuming array arr[l..r] is present

-1 otherwise

{
    if (r >= l)
    {
        int mid = l + (r - l) / 2;
 
        // If element is present at middle
        if (arr[mid] == x)
            return mid;
 
        // If element is smaller than middle
        if (arr[mid] > x)
            return binarysearch1(arr, l, mid - 1, x);
 
        // Else element is in right subarray
        return binarysearch1(arr, mid + 1, r, x);
    }
 
    // When element is not present in array
    return -1;
}

binarysearch2()

int binarysearch2	(	const int *	arr,
		int	l,
		int	r,
		int	x
	)

Iterative implementation.

Parameters

[in]	arr	array to search
	l	left index of search range
	r	right index of search range
	x	target value to search for

Returns

location of x assuming array arr[l..r] is present

-1 otherwise

{
    int mid = l + (r - l) / 2;
 
    while (arr[mid] != x)
    {
        if (r <= l || r < 0)
            return -1;
 
        if (arr[mid] > x)
            // If element is smaller than middle
            r = mid - 1;
        else
            // Else element is in right subarray
            l = mid + 1;
 
        mid = l + (r - l) / 2;
    }
 
    // When element is not present in array
    return mid;
}