WHCSRL 技术网

c语言二分法查找数组中的数据 2021-10-29

C语言折半查找
题目:折半查找,在从小到大的数组中查找关键字key,找到其返回下标,失败则返回-1。
注意:一定要数组有序,否则没有这种算法,只可以从头到尾遍历。
代码:

#include<stdio.h>
#include<assert.h>
//折半查找(二分查找,一定数组有序)  时间复杂度O(logn)
int BinSearch(int arr[], int len, int key)
{
	assert(arr != NULL); //安全处理机制
	if (NULL == arr)
	{
		return -1;
	}

	int low = 0;   //左边指针
	int high = len - 1;  //右边指针
	int mid;//int mid = (low + high)/2; //每次缩小一半,需要和key比较的中间值

	while (low <= high)//当low和high之间范围内  至少有1个值,则继续比较
	{
		mid = (low + high) / 2;//mid = (high-low)/2 + low;//让mid指向临时的范围中间值

		if (arr[mid] == key)//如果mid指向的值就是key   则直接返回其下标
		{
			return mid;
		}
		else if (arr[mid] < key)  //如果mid指向的值小于key   则要找的key这个值一定在mid的右半边
		{
			low = mid + 1;
		}
		else//如果mid指向的值大于key   则要找的key这个值一定在mid的左半边
		{
			high = mid - 1;
		}
	}

	//此时while循环结束,还没有退出函数,则要找的这个值 一定不存在于这个数组内,则返回-1
	return -1;

}

int main()
{
	int arr[] = { 1,3,4,5,8,10,20,23,36,50 };
	int tmp = BinSearch(arr, sizeof(arr) / sizeof(arr[0]), 8);
	int main()
{
	int arr[] = { 1,3,4,5,8,10,20,23,36,50 };
	int tmp = BinSearch(arr, sizeof(arr) / sizeof(arr[0]), 10);
	//printf("所查找的数字在第%%d个。", tmp);
	if (tmp >=0)
	{
		printf("所查找的数字在第%%d个。", tmp);
	}
	else
	{
		printf("所查找数字不存在。");
	}
}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

运行结果:
(1)当查找的数字为8时:
在这里插入图片描述
(2)当查找的数字为-1时:
在这里插入图片描述

推荐阅读