Demo entry 6644645

search

   

Submitted by oxygen on Oct 05, 2017 at 17:43
Language: C. Code size: 9.5 kB.

/* * * * * * * * * * * * * * * WARNING * * * * * * * * * * * * * * *\
 *  When the length of the searched array is larger than 4352 and  *
 *  the code is compiled in VS's debug mode,the stack of program   *
 *  may overflow because of the setting of VS.					   *
 *  As a result, when the program is compiled in VS's debug mode,  *
 *  we suggest set the project setting at "project setting"->	   *
 *  "Linker"->"System"->"Stack Recursive Size(堆栈保留大小)".Give  *
 *  it a larger value which's at least 5000000.					   *
\* * * * * * * * * * * * * * * WARNING * * * * * * * * * * * * * * */


#define _CRT_SECURE_NO_WARNINGS /* Disable the warning caused by scanf */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Define the max number of entries */
#define MAXNUMOFENTRIES 10000

/*
* Function: GenerateData
* -------------------
* Usage: GenerateData(data, nNumOfEntries);
* -------------------
* Parameters:
*     data -- An integer array which is used to store data.
*     nNumOfEntries -- The number of integers to be generated.
* -------------------
* Brief introduction:
*     This procedure generate integers numbered
*     from 0 to N-1, and store them into data.
*/
void GenerateData(int *data, int nNumOfEntries)
{
	int i;
	for (i = 0; i < nNumOfEntries; i++)
	{
		data[i] = i;
	}
}


/*
* Function: BinarySearchByIteration
* -------------------
* Usage: BinarySearchByIteration(N, data, nLeft, nRight);
* -------------------
* Parameters:
*     N -- The integer to be searched.
*     data -- An integer array which stores the data.
*     nLeft -- The left position of the search range.
*     nRight -- The right position of the search range.
* -------------------
* Brief introduction:
*     This procedure searches the integer N in the data array
*     by Binary Search (Iterative Version).
*     If N is found, this function returns the position of N.
*     Otherwise, this function returns -1.
*/
int BinarySearchByIteration(int N, int *data, int nLeft, int nRight)
{
	int nResult = -1;
	while (1)
	{
		int nMid;
		if (nLeft > nRight)
		{
			/* If left position is larger than right position,
			*  it means N is not in this array,
			*  so break and return -1 */
			break;
		}
		nMid = (nLeft + nRight) / 2;
		if (N < data[nMid])
		{
			/* If N is smaller than the mid position data,
			*  go to the left subarray and continue search*/
			nRight = nMid - 1;
		}
		else if (N > data[nMid])
		{
			/* If N is larger than the mid position data,
			*  go to the right subarray and continue search*/
			nLeft = nMid + 1;
		}
		else
		{
			/* N if found */
			nResult = nMid;
			break;
		}
	}
	return nResult;
}


/*
* Function: BinarySearchByRecursion
* -------------------
* Usage: BinarySearchByRecursion(N, data, nLeft, nRight);
* -------------------
* Parameters:
*     N -- The integer to be searched.
*     data -- An integer array which stores the data.
*     nLeft -- The left position of the search range.
*     nRight -- The right position of the search range.
* -------------------
* Brief introduction:
*     This procedure searches the integer N in the data array
*     by Binary Search (Recursive Version).
*     If N is found, this function returns the position of N.
*     Otherwise, this function returns -1.
*/
int BinarySearchByRecursion(int N, int *data, int nLeft, int nRight)
{
	int nMid;
	if (nLeft > nRight)
	{
		/* If left position is larger than right position,
		*  it means N is not in this array,
		*  so just return -1 */
		return -1;
	}
	nMid = (nLeft + nRight) / 2;
	if (N < data[nMid])
	{
		/* If N is smaller than the mid position data,
		*  go to the left subarray and continue search*/
		return BinarySearchByRecursion(N, data, nLeft, nMid - 1);
	}
	else if (N > data[nMid])
	{
		/* If N is larger than the mid position data,
		*  go to the right subarray and continue search*/
		return BinarySearchByRecursion(N, data, nMid + 1, nRight);
	}
	else
	{
		/* N if found, just return its position */
		return nMid;
	}
}


/*
* Function: SequentialSearchByIteration
* -------------------
* Usage: SequentialSearchByIteration(N, data, nNumOfEntries);
* -------------------
* Parameters:
*     N -- The integer to be searched.
*     data -- An integer array which stores the data.
*     nLeft -- The left position of the search range.
*     nRight -- The right position of the search range.
* -------------------
* Brief introduction:
*     This procedure searches the integer N in the data array
*     by Sequential Search (Iterative Version).
*     If N is found, this function returns the position of N.
*     Otherwise, this function returns -1.
*/
int SequentialSearchByIteration(int N, int *data, int nLeft, int nRight)
{
	int nResult = -1;
	int i;
	for (i = nLeft; i <= nRight; i++)
	{
		/* search N from data[nLeft] to data[nRight] */
		if (data[i] == N)
		{
			/* If N is found, set the result and break */
			nResult = i;
			break;
		}
	}
	return nResult;
}


/*
* Function: SequentialSearchByRecursion
* -------------------
* Usage: SequentialSearchByRecursion(N, data, nLeft, nRight);
* -------------------
* Parameters:
*     N -- The integer to be searched.
*     data -- An integer array which stores the data.
*     nLeft -- The left position of the search range.
*     nRight -- The right position of the search range.
* -------------------
* Brief introduction:
*     This procedure searches the integer N in the data array
*     by Sequential Search (Recursive Version).
*     If N is found, this function returns the position of N.
*     Otherwise, this function returns -1.
*/
int SequentialSearchByRecursion(int N, int *data, int nLeft, int nRight)
{
	if (nLeft > nRight)
	{
		/* If left position is larger than right position,
		*  it means N is not in this array,
		*  so just return -1 */
		return -1;
	}
	/* check the data at the left position (the first data) */
	if (data[nLeft] == N)
	{
		/* If N is found, return its position */
		return nLeft;
	}
	else
	{
		/* The first data is not equal to N,
		*  increase the left position and continue searching next */
		return SequentialSearchByRecursion(N, data, nLeft + 1, nRight);
	}
}


/*
* Function: TestSearchFunction
* -------------------
* Usage: TestSearchFunction(lpDescription,
SearchFunction,
N, data, nLeft, nRight,
K);
* -------------------
* Parameters:
*     lpDescription -- The description of the search function.
*     SearchFunction -- The function which searches and returns the result.
*     N -- The integer to be searched.
*     data -- An integer array which stores the data.
*     nLeft -- The left position of the search range.
*     nRight -- The right position of the search range.
*     K -- Execution times of search function.
* -------------------
* Brief introduction:
*     This procedure tests the SearchFunction and prints its performance.
*     Also, it will return the position of N if N is found.
*     Otherwise, this function returns -1.
*/
int TestSearchFunction(char *lpDescription,
	int(*SearchFunction)(int, int *, int, int),
	int N, int *data, int nLeft, int nRight,
	int K)
{
	int nResult = -1, i;
	clock_t startClock, stopClock, ticks;
	double totalTime, singgleTime;
	startClock = clock();
	for (i = 0; i < K; i++)
	{
		/* call the search function for K times */
		nResult = (*SearchFunction)(N, data, nLeft, nRight);
	}
	stopClock = clock();
	ticks = stopClock - startClock; /* the total ticks */
	totalTime = (double)(ticks) / CLK_TCK; /* the total running time */
	singgleTime = totalTime / K; /* the singgle running time */
	if (nResult != -1)
	{
		printf("%s found %d at %d.\n", lpDescription, N, nResult);
	}
	else
	{
		printf("%s didn't find %d.\n", lpDescription, N);
	}
	printf("Ticks: %lu, TotalTime: %.8lfs, SinggleTime: %.8lfs.\n", ticks, totalTime, singgleTime);
	return nResult;
}


int main()
{
	int data[MAXNUMOFENTRIES];
	int nNumOfEntries;
	int N; /* The integer to be searched*/
	int K; /* Repeat times for testing */

	printf("Please input number of entries: ");
	scanf("%d", &nNumOfEntries);
	if (nNumOfEntries > sizeof(data) / sizeof(int))
	{
		/* If the input is larger than the size of data, report error and exit */
		printf("Error: Number of entries out of range\n");

		system("pause");

		return -1;
	}
	GenerateData(data, nNumOfEntries); /* Generate the test data */

	N = nNumOfEntries;
	printf("N (the integer to be searched) is: %d\n", N);

	printf("Please intput K (the number of loops for testing): ");
	scanf("%d", &K);

	printf("*****************************************************************\n");

	/* Test these four different search functions */
	TestSearchFunction("BinarySearchByIteration",
		BinarySearchByIteration,
		N, data, 0, nNumOfEntries - 1,
		K);
	TestSearchFunction("BinarySearchByRecursion",
		BinarySearchByRecursion,
		N, data, 0, nNumOfEntries - 1,
		K);
	TestSearchFunction("SequentialSearchByIteration",
		SequentialSearchByIteration,
		N, data, 0, nNumOfEntries - 1,
		K);
	TestSearchFunction("SequentialSearchByRecursion",
		SequentialSearchByRecursion,
		N, data, 0, nNumOfEntries - 1,
		K);

	printf("*****************************************************************\n");

	system("pause");

	return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).