查找 -- 对半查找法（递归）.txt

包括数据结构中的常见的排序

/******************************************************************************************************
** Program Name : Insertion Sort In The Form Of Recursion
** 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 left, int right) ;

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, 0, MAX_SIZE-1) ;

	}

	return 0 ;
}

void Half_Search(const int *a, int SIZE, int value, int left, int right)
{
	if (left > right || value < a[left] || value > a[right] )
	{
		cout << "No Such Data Found!" << endl << endl ;
		return ;
	}
	
	int  middle = (left + right)/2 ;			// middle pointer

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

		cout << "_________________Data Found___________________" << 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 << "_________________Data Found___________________" << endl ;
	}
	else if (value < a[middle] )
		Half_Search(a, SIZE, value, left, middle-1) ;
	else
		Half_Search(a, SIZE, value, middle+1, right) ;
	
}


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