查找 -- 对半查找法（非递归）[anank].cpp

包含了二叉树查找法

/******************************************************************************************************
** Program Name : Insertion Sort
** Author       : Lu Jian Hua
** Time         : 2007-9-5 
*******************************************************************************************************/

#include <iostream>
using namespace std ;

const int MAX_SIZE = 20;

void Half_Search(const int *a, int SIZE, int value) ;

int main()
{
	int value = 0 ;

	cout << "---------------------- Half Search ------------------------" << endl << endl ;
	
	int a[MAX_SIZE] =	{
							1,  2,  3,  4,  4,
							4,  7,  7,  9, 10,
							11, 12, 13, 13,15,
							16, 17, 18, 19,20
						} ;

	
	for (int i=0; i<20; i++)
		cout << "a[" << i << "] : " << a[i] << endl ;

	while (true)
	{
		cout << "\n\nPlease Enter The Value You Want To Find : " ;
		cin  >> value ;
		cout << endl ;

		Half_Search(a, MAX_SIZE, value) ;

	}

	return 0 ;
}

void Half_Search(const int *a, int SIZE, int value)
{
	int  left    = 0 ;						// left   pointer
	int  right   = SIZE-1 ;					// right  pointer
	int  middle  = 0 ;						// middle pointer
	bool Is_Find = false ;

	while (left <= right)					// if left > right, then exit
	{
		middle = (left + right)/2 ;
		if ( value == a[middle] )
		{
			Is_Find = true ;
			break ;
		}
		else if (value < a[middle] )
			right = middle-1 ;
		else
			left = middle+1 ;
	}

	if (Is_Find)
	{
		while (a[--middle] == value) ;		// move the pointer to the front position of the leftest certain data

		cout << "________________________________________________" << endl ;

		while (a[++middle] == value && middle < SIZE)		// print all the data(the count can be one, two, three...)
			cout << "a[" << middle << "] : " << a[middle] << endl ;
		
		cout << "________________________________________________" << endl ;
	}
	else
		cout << "No Such Data Found!" << endl << endl ;
}


/********************************************************************************
*
* Notice : This Program Can Be Launched In VC6.0 Environment
*
********************************************************************************/