顺序查找

猜数游戏

从键盘中任意输入一个数，判断数列中是否包含该数【顺序查找】要求: 如果找到了，就提示找到，并给出下标值, 找不到提示没有。

首先对整个数组进行遍历，如果相等返回数组下标

//遍历
int i;
for (i = 0; i < arrLen; i++) {
	if (arr[i] == val) {
		return i;
	}
}
//如果在for循环中没有找到，则返回-1;
return -1;

main方法中，arrLen使用sizeof()方法可以得到，并且用index获取方法的返回值

int arr[] = { 23,1,34,88,100 };
int arrLen = sizeof(arr) / sizeof(int);
int index = seqSearch(arr, arrLen, 10);
if (index != -1) {
	printf("找到了，当前下标值为%d", index);
		
}
else {
	printf("没有找到该数据！");
}
getchar();

完整代码

//顺序查找
#include<stdio.h>

int seqSearch(int arr[], int arrLen, int val) {
	//遍历
	int i;
	for (i = 0; i < arrLen; i++) {
		if (arr[i] == val) {
			return i;
		}
	}
	//如果在for循环中没有找到，则返回-1;
	return -1;
}

void main() {

	int arr[] = { 23,1,34,88,100 };
	int arrLen = sizeof(arr) / sizeof(int);
	int index = seqSearch(arr, arrLen, 10);
	if (index != -1) {
		printf("找到了，当前下标值为%d", index);
		
	}
	else {
		printf("没有找到该数据！");
	}
	getchar();
}

二分查找

请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ，
输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示”没有这个数”。二分查找的前提是，该数组是一个有序数组

思路分析

比如我们要查找的数是findVal
如果midVal > findVal 说明，应该在midVal 的左边查找
如果midVal < findVal 说明，应该在midVal 的右边查找
如果midVal == findVal，说明找到

二分查找方法的具体实现

先找到数组中间这个数的下标，两者相加/2得到的是中间的位置，中间位置对应的就是数组的中间值

int midIndex = (leftIndex + rightIndex) / 2; 
int midVal = arr[midIndex];

之后进行递归操作

//如果midVal >  findVal 说明， 应该在midVal 的左边查找
if(midVal > findVal) {
	binarySearch(arr, leftIndex, midIndex-1, findVal);//!!!
} else if(midVal < findVal){//如果midVal <  findVal 说明， 应该在midVal 的右边查找
	binarySearch(arr, midIndex+1, rightIndex, findVal);//!!!
} else {
	return midIndex; //返回该数的下标
}

递归操作之后，如果左边的下标值大于右边的下标值，则说明这个数组都比较过，但还是没有找到

if( leftIndex > rightIndex) {
	return -1;//!!!!
}

二分查找的完整代码

//二分查找
#include<stdio.h>

//二分查找
int binarySearch(int arr[], int leftIndex, int rightIndex, int findVal) {
	
	
	//先找到数组中间这个数 midVal
	int midIndex = (leftIndex + rightIndex) / 2; 
	int midVal = arr[midIndex];
	//如果leftIndex > rightIndex, 说明这个数组都比较过，但是没有找到
	if( leftIndex > rightIndex) {
		return -1;//!!!!
	}
	//如果midVal >  findVal 说明， 应该在midVal 的左边查找
	if(midVal > findVal) {
		binarySearch(arr, leftIndex, midIndex-1, findVal);//!!!
	} else if(midVal < findVal){//如果midVal <  findVal 说明， 应该在midVal 的右边查找
		binarySearch(arr, midIndex+1, rightIndex, findVal);//!!!
	} else {
		return midIndex; //返回该数的下标
	}


}

void main() {

	int arr[] = { 1,8, 10, 89, 1000, 1234 };
	int arrLen = sizeof(arr) / sizeof(int);
	int index = binarySearch(arr, 0, arrLen - 1, 1000);
	if (index != -1) {
		printf("找到 index = %d", index);
	}
	else {
		printf("没有找到");
	}
	getchar();
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/83268.html