Binary Search is a significant improvement over sequential (serial) search but this improvement comes at a price: Each data element must be random-access (e.g. stored or indexed in an array) and the collection must be pre-sorted.

Here is a simple Java program to demonstrate both an iterative and a recursive version of binary search over an array of "int"s.

// Demonstrate recursive and iterative versions of binary search.
// Both versions have same specifications.
// Precondition: data stored in array in ascending order.
// Arguments: the int array, index of first element, number of elements, 
// target value
// Returns: If target matched, returns index of matching element. If target 
// not matched, returns -1.
public class BinSearch
{
	public static void main(String[] args)
	{
		final int SIZE = 10;
		int target = 18;
		int [] stuff = new int[SIZE];
		for (int i=0; i<SIZE; i++) stuff[i] = i * 3;
		System.out.println(ReSearch(stuff,0,SIZE,target));
		System.out.println(ItSearch(stuff,0,SIZE,target));
	}

	// Recursive version
	public static int ReSearch(int [] a, int first, int size, int target)
	{
		int middle;
		if (size <=0)
			return -1;
		else
		{
			middle = first + size/2;
			if (target == a[middle])
				return middle;
			else if (target < a[middle])
				return ReSearch(a, first, size/2, target);
			else
				return ReSearch(a, middle+1, (size-1)/2, target);
		}
	}

	// Iterative version
	public static int ItSearch(int [] a, int first, int size, int target)
	{
		int middle;
		
		while (size > 0)
		{
			middle = first + size/2;
			if (target == a[middle])
				return middle;
			else if (target < a[middle])
			{
				size = size/2;
			}
			else
			{
				size = (size-1)/2;
				first = middle+1;
			}
		}
		return -1;
	}
}

Trace the call to the recursive version, ReSearch, with evaluated arguments shown:

ReSearch(a, 0, 10, 18)
first is 0
size is 10
target is 18
middle is 0 + 10/2 = 5
a[5] is 15
18 > 15 so recurse
ReSearch(a, 6, 4, 18) // middle+1, (size-1)/2
first is 6
size is 4
target is 18
middle is 6 + 4/2 = 8
a[8] is 24
18 < 24 so recurse
ReSearch(a, 6, 2, 18) // first, size/2
first is 6
size is 2
target is 18
middle is 6 + 2/2 = 7
a[7] is 21
18 < 21 so recurse
ReSearch(a, 6, 1, 18) // first, size/2
first is 6
size is 1
target is 18
middle is 6 + 1/2 = 6
a[6] is 18
18 == 18 so return 6
return 6
return 6
return 6

Consider a worst case situation: target is not found

Trace the call to the recursive version, ReSearch, with evaluated arguments shown:

ReSearch(a, 0, 10, 19)
first is 0
size is 10
target is 19
middle is 0 + 10/2 = 5
a[5] is 15
19 > 15 so recurse
ReSearch(a, 6, 4, 19) // middle+1, (size-1)/2
first is 6
size is 4
target is 19
middle is 6 + 4/2 = 8
a[8] is 24
19 < 24 so recurse
ReSearch(a, 6, 2, 19) // first, size/2
first is 6
size is 2
target is 19
middle is 6 + 2/2 = 7
a[7] is 21
19 < 21 so recurse
ReSearch(a, 7, 1, 19) // first, size/2
first is 7
size is 1
target is 19
middle is 7 + 1/2 = 7
a[7] is 21
19 < 21 so recurse
ReSearch(a, 7, 0, 19) // first, size/2
size is 0 so return -1

How many calls? 5

How many values in array? 10

Suppose number of values were doubled. How many additional calls? Estimate the Big-O based on this.

Trace the call to the iterative version, ItSearch, with evaluated arguments shown:

ItSearch(a, 0, 10, 18)
first is 0
size is 10
target is 18
middle is 0 + 10/2 = 5
a[5] is 15
18 > 15 so set size = (size-1)/2;first = middle+1;
first is 6
size is 4
middle is 6 + 4/2 = 8
a[8] is 24
18 < 24 so set size = size/2;
size is 2
middle is 6 + 2/2 = 7
a[7] is 21
18 < 21 so set size = size/2;
size is 1
middle is 6 + 1/2 = 6
a[6] is 18
18 == 18 so return 6

Similar pattern for worst case, e.g. target is 19.

Why, when target is in the upper half, is size reset to (size-1)/2 where when target is in first half, size is reset to size/2???? What is the difference?

Difference is this: when size is even, there is no "middle" element so we choose the middle to be the first element in the (new) second half. The second half in effect becomes one element shorter than the first half, and the size needs to reflect this.

Do Big-O analysis.

[ Lectures | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Peter Sanderson ( PeteSanderson@smsu.edu )