二分查找算法（循环实现与递归实现）（C语言实现）

算法思想

前提：有序数组中查找关键词所在的位置

①：确定整个查找区间的中间位置Mid = (Min + Max) / 2

② 用查找的数据与中间位置的数据进行比较；

若相等，则查找成功

若小于，则把查找的范围缩小到上次查找中间的左半区域
Max = Mid - 1;
确定整个查找区间的中间位置Mid = (Min + Max) / 2

若大于，则把查找的范围缩小到上次查找中间的左半区域
Min = Mid + 1;
确定整个查找区间的中间位置Mid = (Min + Max) / 2

③ 对缩小区域重复上述步骤。

图解

上面过程是对于下面使用循环实现二分查找的过程排序，递归类似。

代码

循环实现

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

int main()
{
	int arr[10] = { 1,23,42,55,59,75,80,92,101,106 };
	int findData = 42;
	int sig = 0;
	int Min = 0;
	int Max = sizeof(arr) / sizeof(arr[0]) - 1;
	int Mid = 0;
	while (Min<=Max)
	{
		Mid = (Max + Min) / 2;
		if (findData == arr[Mid])
		{
			sig = 1;
			printf("arr[%d]:%d == findData:%d\n", Mid, arr[Mid], findData);
			break;
		}
		else if (findData > arr[Mid])
		{
			Min = Mid + 1;
		}
		else if (findData < arr[Mid])
		{
			Max = Mid - 1;
		}
	}
	if (sig == 0)
	{
		printf("no find\n");
	}
	return 0;
}

递归实现

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
void HalfSreach(int arr[], int Min, int Max, int FindData)
{
	if (Min > Max)
	{
		printf("no find\n");
		exit(0);
	}
	int Mid = (Min + Max) / 2  -1;
	if (arr[Mid] == FindData)
	{
		printf("arr[%d]:%d == findData:%d\n", Mid, arr[Mid], FindData);
		exit(0);
	}
	else if (FindData >arr[Mid] )
	{
		HalfSreach(arr, Mid + 1, Max, FindData);
	}
	else {
		HalfSreach(arr, Min, Mid - 1, FindData);
	}
}


int main112()
{
	int arr[10] = { 1,23,42,55,59,75,80,92,101,106 };
	int ArrLen = sizeof(arr) / sizeof(arr[0]);
	int Min = 0;
	HalfSreach(arr,Min,ArrLen,101);
	return 0;
}

运行测试

循环实现测试结果

递归实现测试结果

说明

时间复杂度：logn