【C语言】自定义函数对有序数组的二分查找，以及对二分查找会出现的问题进行补充

旧城等待， 2023-10-15 15:39 3阅读 0赞

### 一、编写main函数 ###

int main()
    {
    	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
    	int k = 0;
    	scanf("%d", &k);
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	int ret = binary_search(arr, k, sz); //自定义函数
    	if (ret == -1)
    	{
    		printf("找不到\n");
    	}
    	else
    	{
    		printf("找到了，下标为：%d\n", ret);
    	}
    	return 0;
    }

> 需要注意的是， 由于数组传输的是**首地址**，因此需要在main主调函数中提前计算出数组的大小（**即sz**）并传入binary\_search函数。
> 
> 不直接判断ret == 0而是ret == -1是因为可能要查找的值的下标就为0，因此-1更加合适。

### 二、binary\_search函数的编写 ###

int binary_search(int arr[], int k, int sz)
    {
    	int left = 0;
    	int right = sz - 1;
    	while (left <= right)
    	{
    		int mid = (left + right) / 2;
    		if (arr[mid] > k)
    			right = mid - 1;
    		else if (arr[mid] < k)
    			left = mid + 1;
    		else
    		{
    			return mid;
    		}
    
    	}
    	return -1;
    }

> 对应的设置好left和right的范围。其中需要注意的是int mid = (left + right) / 2;必须放在循环内部，放在循环外mid就无法实时更新。

--------------------

### 三、二分查找会出现的问题的补充说明 ###

> int mid = (left + right) / 2;取平均值的方法，有时候是**不靠谱**的，因为当left和right非常大时，它们相加将会超出int能承受的最大值，就会造成溢出。当发生溢出时它们相加再相除的值便不再是它们俩的平均值。
> 
> 当然千万不能简单的觉得既然int溢出了，那用longlong就好了，那要是longlong也溢出了该怎么办，很显然这种处理方式是不对的。

> 而有一种方式是，假设一个柱子a高度是a，柱子b高度是b，如果希望柱子高度能一样高，可以将柱子b高出的部分分配一半给柱子a，便能够达到平分的操作。

![8c1d0614858542a6840eb474f11b4fa6.png][]

> 因此在求平均值时，可以用这种方法从而避免溢出。即int mid = left + (right - left) / 2;

![314c1cbc38cb43c6942ebcc469c74d1a.png][]

--------------------

如果觉得作者写的不错，求给作者一个大大的点赞支持一下，你们的支持是我更新的最大动力！

[8c1d0614858542a6840eb474f11b4fa6.png]: https://img-blog.csdnimg.cn/8c1d0614858542a6840eb474f11b4fa6.png
[314c1cbc38cb43c6942ebcc469c74d1a.png]: https://img-blog.csdnimg.cn/314c1cbc38cb43c6942ebcc469c74d1a.png