关于二分搜索

关于二分搜索

1. 算法思想

在有序数组中，将要查找的元素与数组中的中间项比较，若要找的数据小于中间项，则搜索数组的前半部分；若要找的数据大于中间项，则搜索数组的后半部分即可。每次比较都将使搜索范围减少一半。

2. 伪代码

Set first to 0 //令first的初值为0

Set last to lenght-1 //令last的初值为lenght（数组的长度）-1

Set found to False //令found的初值为False

WHILE(first

Set middle to (first+last)/2 //令middle（中间项）的初值为

(first+last)/2

IF(item equals data[middle])//如果item（要查找的元素）=中间项

    Set found to True //令found的值为True

Else             //如果item（要查找的元素）！=中间项

    IF(item

        Set last to middle-1//令last=middle-1

    ELSE                   //如果item大于中间项

        Set first to middle+1//令first=middle+1

Return found               //返回found

3. 流程图

4. 桌面测试

给出8个元素组成的有序数组A，例如：8 13 17 26 44 55 88 97，如图8所示：

查找数据88，查找过程如下：

1. 判断数据88是否与A[3]相等，不等，且88>A[3]=26，向下移动到A[4]-A[7]；
2. 判断数据88是否与A[5]相等，不等，且88>A[5]=55，向下移动到A[6]-A[7]；
3. 判断数据88是否与A[6]相等，相等；
4. 输出查找结果，A[6]=88。

5. 程序设计

#include
int main()
{
	int first = 0, last, middle;
	int length, n;
	int A[100];
	printf("请输入数组的长度：");
	scanf("%d", &length);
	last = length - 1;
	printf("请输入需要排序的数组：");
	for (int i = 0; i < last; i++)
	{
		scanf("%d", A[i]);
	}
	printf("请输入要查找的数值：");
	scanf("%d", &n);
	while (first < last)
	{
		middle = (first + last) / 2;
		if (n == A[middle])
		{
			printf("A[%d]=%d", middle, n);
		}
		else if (n < A[middle])
		{
			last = middle - 1;
		}
		else
		{
			first = middle + 1;
		}
	}
	if (first >= last && A[middle] != n)
	{
		printf("Not Fpund!");
	}
	return 0;
}

6. 程序运行测试

(1)

 

(2)