Notes 5a:
Addendum A to Essential of Data Structures, Cpt 5

Math 61 -- D. C. Smolarski, S.J.
Santa Clara University, Department of Mathematics and Computer Science

Contents

• Linear Search
• Binary Search

Linear Search

This is one version of a function that uses linear search to find an item in an array. (cf. Ford and Topp, p 73, 161). The code's flow differs slightly from that given in DCS, because C++ has a return statement which Pascal does not have. As a result, in C++ it is possible to return to the calling code from the middle of a loop when one has found the desired item, instead of existing the loop and then returning, as is required in Pascal.

	int SeqSearch(int list[], int LastElIndex, int key)
	{
	   for(int i=0; i < LastElIndex; i++)
		if (list[i] == key)
		   return i;    // return index of match
	   return -1;		// search failed. return -1
	}

Binary Search

This code is taken from Ford and Topp, p 163. Note that whereas DCS uses F(irst) and L(ast), F&T uses low and high.

	int BinSearch(int list[], int low, int high, int key)
	{
	   int mid;

	   while (low <= high)
	   {
		mid = (low + high)/2;
		if (key == list[mid])
		   return mid;
		else if (key < list[mid])
		   high = mid-1;
		else
		   low = mid+1;
	   }
	   return -1;		//did not find item
	}

This page is maintained by Dennis C. Smolarski, S.J.
© Copyright 1998, 1999 Dennis C. Smolarski, SJ, All rights reserved.
Last changed: 29 March 1998.