1. the average time
2. the worst-case time and
3. the best possible time.

If there are n items in our collection - whether it is stored as an array or as a linked list - then it is obvious that in the worst case, when there is no item in the collection with the desired key, then n comparisons of the key with keys of the items in the collection will have to be made.

In binary search, we first compare the key with the item in the middle position of the array. If there's a match, we can return immediately. If the key is less than the middle key, then the item sought must lie in the lower half of the array; if it's greater then the item sought must lie in the upper half of the array. So we repeat the procedure on the lower (or upper) half of the array.

Our FindInCollection function can now be implemented:

static void *bin_search( collection c, int low, int high, void *key ) {
	int mid;
	/* Termination check */
	if (low > high) return NULL;
	mid = (high+low)/2;
	switch (memcmp(ItemKey(c->items[mid]),key,c->size)) {
		/* Match, return item found */
		case 0: return c->items[mid];
		/* key is less than mid, search lower half */
		case -1: return bin_search( c, low, mid-1, key);
		/* key is greater than mid, search upper half */
		case 1: return bin_search( c, mid+1, high, key );
		default : return NULL;
		}
	}

void *FindInCollection( collection c, void *key ) {
/* Find an item in a collection
   Pre-condition: 
	c is a collection created by ConsCollection
	c is sorted in ascending order of the key
	key != NULL
   Post-condition: returns an item identified by key if
   one exists, otherwise returns NULL
*/
	int low, high;
	low = 0; high = c->item_cnt-1;
	return bin_search( c, low, high, key );
}

1. bin_search is recursive: it determines whether the search key lies in the lower or upper half of the array, then calls itself on the appropriate half.
2. There is a termination condition (two of them in fact!)
   1. If low > high then the partition to be searched has no elements in it and
   2. If there is a match with the element in the middle of the current partition, then we can return immediately.
3. AddToCollection will need to be modified to ensure that each item added is placed in its correct place in the array. The procedure is simple:
   1. Search the array until the correct spot to insert the new item is found,
   2. Move all the following items up one position and
   3. Insert the new item into the empty position thus created.
4. bin_search is declared static. It is a local function and is not used outside this class: if it were not declared static, it would be exported and be available to all parts of the program. The static declaration also allows other classes to use the same name internally.

   static reduces the visibility of a function an should be used wherever possible to control access to functions!

Analysis

Each step of the algorithm divides the block of items being searched in half. We can divide a set of n items in half at most log2 n times. Thus the running time of a binary search is proportional to log n and we say this is a O(log n) algorithm.

Binary search requires a more complex program than our original search and thus for small n it may run slower than the simple linear search. However, for large n, Thus at large n, log n is much smaller than n, consequently an O(log n) algorithm is much faster than an O(n) one.

Plot of n and log n vs n .