数据结构 C 代码 9.1: 顺序查找与二分查找

摘要: 二分查找的效率是我们追求的目标.

先上代码, 再说废话.

#include 
#include 


typedef struct Node{
	int key;
	char value;
}Node, *NodePtr;


typedef struct SequentialList{
	int length;
	NodePtr elements;
}SequentialList, *ListPtr;


ListPtr initList(int* paraKeys, char* paraValues, int paraLength){
	int i;
	ListPtr resultPtr = (ListPtr)malloc(sizeof(struct SequentialList));
	resultPtr->length = paraLength;
	resultPtr->elements = (NodePtr)malloc((paraLength + 1) * sizeof(struct Node));
	for (i = 0; i < paraLength; i ++){
		//printf("setting key for index %d: %d and value: %crn", i, paraKeys[i], paraValues[i]);
		resultPtr->elements[i + 1].key = paraKeys[i];
		resultPtr->elements[i + 1].value = paraValues[i];
	}//Of for i

	return resultPtr;
}//Of initList


char sequentialSearch(ListPtr paraListPtr, int paraKey){
	int i = paraListPtr->length;
	paraListPtr->elements[0].key = paraKey;
	paraListPtr->elements[0].value = 'x';

	while(paraListPtr->elements[i].key != paraKey){
		i--;
	}//Of while

	return paraListPtr->elements[i].value;
}//Of sequentialSearch


void sequentialSearchTest() {
	int tempUnsortedKeys[] = { 4, 5, 3, 6, 10, 7, 1, 9 };
	char tempContents[] = { 'h', 'e', 'l', 'o', 'w', 'r', 'd', "!" };
	ListPtr tempListPtr = initList(tempUnsortedKeys, tempContents, 8);

	printf("Search result of 10 is: %crn", sequentialSearch(tempListPtr, 10));
	printf("Search result of 5 is: %crn", sequentialSearch(tempListPtr, 5));
	printf("Search result of 4 is: %crn", sequentialSearch(tempListPtr, 4));
	printf("Search result of 2 is: %crn", sequentialSearch(tempListPtr, 2));
}// Of sequentialSearchTest


char binarySearch(ListPtr paraListPtr, int paraKey){
	int tempLeft = 1;
	int tempRight = paraListPtr->length;
	int tempMiddle = (tempLeft + tempRight) / 2;

	while (tempLeft <= tempRight) {
		tempMiddle = (tempLeft + tempRight) / 2;
		if (paraListPtr->elements[tempMiddle].key == paraKey) {
			return paraListPtr->elements[tempMiddle].value;
		} else if (paraListPtr->elements[tempMiddle].key <= paraKey) {
			tempLeft = tempMiddle + 1;
		} else {
			tempRight = tempMiddle - 1;
		}//Of if
	} // Of while

	// Not found.
	return 'x';
}//Of binarySearch


void binarySearchTest() {
	int tempUnsortedKeys[] = { 1, 3, 4, 5, 6, 7, 9, 10 };
	char tempContents[] = { 'h', 'e', 'l', 'o', 'w', 'r', 'd', "!" };
	ListPtr tempListPtr = initList(tempUnsortedKeys, tempContents, 8);

	printf("Search result of 10 is: %crn", binarySearch(tempListPtr, 10));
	printf("Search result of 5 is: %crn", binarySearch(tempListPtr, 5));
	printf("Search result of 4 is: %crn", binarySearch(tempListPtr, 4));
	printf("Search result of 2 is: %crn", binarySearch(tempListPtr, 2));
}// Of binarySearchTest
	

int main(){
	printf("rn-------sequentialSearchTest-------rn");
	sequentialSearchTest();

	printf("rn-------binarySearchTest-------rn");
	binarySearchTest();
	return 1;
}// Of main

-------sequentialSearchTest-------
Search result of 10 is: w
Search result of 5 is: e
Search result of 4 is: h
Search result of 2 is: x

-------binarySearchTest-------
Search result of 10 is: !
Search result of 5 is: o
Search result of 4 is: l
Search result of 2 is: x
Press any key to continue

1. 顺序查找有个哨兵, 否则代码也太简单了吧.
2. 折半查找虽然看似简单, 但容易写错. 时间复杂度只有 O ( log ⁡ n ) O(log n) O(logn), 简直不要太快!