C语言经典算法之二分查找详解

目录

• • >1 . 算法思想：
  • > 2 . 查找步骤：
  • >3 . 图解
  • >4 . 代码演示：

>1 . 算法思想：

二分查找又称折半查找，适合对已经排好序的数据集合进行查找，时间复杂度为O(log2n),效率高。对一升序的数据集合，先找出升序数据集合最中间的元素，将数据划分为两个子集，将最中间的元素和关键字进行比较，如果相等则返回，如果大于关键字，则在前一个数据子集中查找，如果想小于反之，直至找到为止

> 2 . 查找步骤：

(1) 首先确定查找区间的中间位置（假定是一个升序的数组），那么mid = left + ( right - left ) / 2 ;
//为了防止越界
(2) 用待查找值与中间位置值进行比较，若相等，则找到，输出
(3) 若大于，则在后半区域中继续进行折半查找
(4) 若小于，则在前半区域中继续进行折半查找
(5) 查找成功，则返回数值的数组下标

>3 . 图解

假设查找数组int arr[] = {1，2，3，4，5，6，7，8，9，10}中的数值7

分析：一共经历三次查找，四处left=right时查找结束。第一次mid=4,5小于7，则left=mid+1=5,继续在右侧折半查找，第二次mid=7，8大于7，则right=mid-1=6，第三次mid=5,6小于7，left=mid+1=6,此时left=right,找到7，下标为6

>4 . 代码演示：

int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 7;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int left = 0;
	int right = sz - 1;

	while (left<=right)
	{
		//int mid = (left + right) / 2;
		int mid = left + (right - left) / 2;//防止数据过大，越界

		if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下标是:%d\n", mid);
			break;
		}
	}
	if (left > right)
		printf("找不到\n");

	return 0;
}

运行结果：