整形有序数组查找--遍历法与折半法/二分法

通过C语言来实现数组元素的查找

查找数组元素，如果找到了，就输出它的下标，找不到的话就输出“找不到这个数”

遍历法

将所要查找的数与数组中从第一个元素开始进行比较，若遍历完数组所有元素都没有与要找的的元素相同，则数组中不存在这个数；若在遍历中，有相同的元素存在，则存在这个数。

因为进行比较是一个不断重复的过程，所以这里用循环

#include<stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int i;
	int k = 6;       //所要查找的元素k
	for (i = 0; i < 10; i++)
	{
		if (k==arr[i])
		{
			printf("这个数的下标是%d\n", i);
			break;      //找到之后直接跳出循环
		}
	}
	if (10 == i)    //如果遍历完整个数组都未找到时，跳出循环后i的值就已经是1了
	{
		printf("找不到这个数\n");
	}
}

运行结果：

但因为遍历法它的计算复杂度太高(复杂度最高为N)，我们一般采用折半法/二分法来实现（复杂度最高为Log2  N）（N为数组元素个数）

实现代码如下

#include<stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 3;
    int size = sizeof(arr) / sizeof(arr[0]);   //计算数组元素个数
	int left = 0;
	int right = size - 1;       //最右边元素下标
	int mid;                    //中间元素下标
	while (left <= right)
	{
	    mid = (left + right) / 2;
		if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else
		{
			printf("这个数的下标是%d\n", mid);
			break;
		}
	}
	if (left > right)         //在left与right发生交叉，即left>right时说明没有找到
	{
		printf("找不到这个数\n");
	}
	return 0;
}

运行结果：

用二分法查找，每次都将查找范围缩小一半，效率较高