C语言：写一个函数，实现一个整型有序数组的二分查找-Toy模板网

这篇具有很好参考价值的文章主要介绍了C语言：写一个函数，实现一个整型有序数组的二分查找。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

写一个函数，实现一个整型有序数组的二分查找，找出要找的数字在数组中对应的下标。

=========================================================================

思路：

总体思路：

（一）自定义函数部分：



（1）.

参数：

int arr[] -- 数组首地址

int k -- 要在数组中找的数字

int sz -- 数组长度



定义左右下标；

（2）.

使用二分查找法；

（二）主函数部分：

定义有序数组，设置要查找的值，求出数组元素个数。

调用自定义函数。

判断自定义函数的返回值，打印相应的情况。



自定义函数部分：

第一步：

（1）. 形参的设置：

int arr[] -- 数组首地址；

int k -- 要在数组中找的数字；

int sz -- 数组长度。

（2）. 定义左右下标 -- left 和 right

实现代码：
#include <stdio.h>

int binary_search(int arr[], int k, int sz)//形参
{
	int left = 0; //左下标
	int right = sz - 1; //右下标


}

int main()
{

	return 0;
}
实现图片：

第二步：

使用二分查找方法：

（1）. 使用while循环。

（2）. 生成中间值下标 mid ：

int mid = left + (right - left) / 2;

left 是小的一边，（right - left）是两者的差值，（right - left）/ 2 是差值的一半，

left + (right - left) / 2，即小的一边加上差值的一半，

这时两边是一样的，任意一边都是平均值（中间值）

（3）.

如果中间值小于要找的值，

舍弃中间值和中间值左边的所有数，调整左下标left ：left = mid + 1。

如果中间值大于要找的值，

舍弃中间值和中间值右边的所有数，调整右下标right ：right = mid - 1。

如果中间值等于要找的值，

返回中间值下标mid。

（4）. 找不到则返回 -1 。

实现代码：
int binary_search(int arr[], int k, int sz)//形参
{
	int left = 0; //左下标
	int right = sz - 1; //右下标

	//使用while循环
	while (left <= right)
	{
		//生成中间值下标 mid ：
		int mid = left + (right - left) / 2;

		//二分查找:
		if (arr[mid] < k)//中间值 小于 要找的值
		{
			left = mid + 1;
			//舍弃中间值和中间值左边的所有数，
			//调整 左下标left ：left = mid + 1。
		}
		else if (arr[mid] > k)//中间值 大于 要找的值
		{
			right = mid - 1;
			//舍弃中间值和中间值右边的所有数，
			//调整 右下标right ：right = mid - 1。
		}
		else if (arr[mid] == k)//中间值 等于 要找的值
		{
			return mid;
			//返回中间值下标mid。
		}
	} 
	if (left > right)
	{
		return -1; //找不到则返回-1
	}
}
实现图片：

主函数部分：

（1）. 定义有序数组，设置要查找的值，求出数组元素个数。

（2）. 调用自定义函数。

（3）. 判断自定义函数的返回值，打印相应的情况。

实现代码：
#include <stdio.h>

int binary_search(int arr[], int k, int sz)//形参
{
	int left = 0; //左下标
	int right = sz - 1; //右下标

	//使用while循环
	while (left <= right)
	{
		//生成中间值下标 mid ：
		int mid = left + (right - left) / 2;

		//二分查找:
		if (arr[mid] < k)//中间值 小于 要找的值
		{
			left = mid + 1;
			//舍弃中间值和中间值左边的所有数，
			//调整 左下标left ：left = mid + 1。
		}
		else if (arr[mid] > k)//中间值 大于 要找的值
		{
			right = mid - 1;
			//舍弃中间值和中间值右边的所有数，
			//调整 右下标right ：right = mid - 1。
		}
		else if (arr[mid] == k)//中间值 等于 要找的值
		{
			return mid;
			//返回中间值下标mid。
		}
	} 
	if (left > right)
	{
		return -1; //找不到则返回-1
	}
}

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; //定义有序数组
	int k = 7; //设置要查找的值
	int sz = sizeof(arr) / sizeof(arr[0]); //求出数组元素个数
	// 整个数组大小 / 单个数组元素大小 = 数组元素个数

	//调用自定义函数：
	int ret = binary_search(arr, k, sz); //ret接收返回的下标

	//判断自定义函数的返回值，打印相应的情况：
	if (ret == -1) //未找到，返回-1
	{
		printf("找不到\n");
	}
	else
	{
		printf("找到了，下标是：%d\n", ret);
	}

	return 0;
}
实现图片：

最终代码和实现效果

最终代码：

#include <stdio.h>

int binary_search(int arr[], int k, int sz)//形参
{
	int left = 0; //左下标
	int right = sz - 1; //右下标

	//使用while循环
	while (left <= right)
	{
		//生成中间值下标 mid ：
		int mid = left + (right - left) / 2;

		//二分查找:
		if (arr[mid] < k)//中间值 小于 要找的值
		{
			left = mid + 1;
			//舍弃中间值和中间值左边的所有数，
			//调整 左下标left ：left = mid + 1。
		}
		else if (arr[mid] > k)//中间值 大于 要找的值
		{
			right = mid - 1;
			//舍弃中间值和中间值右边的所有数，
			//调整 右下标right ：right = mid - 1。
		}
		else if (arr[mid] == k)//中间值 等于 要找的值
		{
			return mid;
			//返回中间值下标mid。
		}
	} 
	if (left > right)
	{
		return -1; //找不到则返回-1
	}
}

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; //定义有序数组
	int k = 7; //设置要查找的值
	int sz = sizeof(arr) / sizeof(arr[0]); //求出数组元素个数
	// 整个数组大小 / 单个数组元素大小 = 数组元素个数

	//调用自定义函数：
	int ret = binary_search(arr, k, sz); //ret接收返回的下标

	//判断自定义函数的返回值，打印相应的情况：
	if (ret == -1) //未找到，返回-1
	{
		printf("找不到\n");
	}
	else
	{
		printf("找到了，下标是：%d\n", ret);
	}

	return 0;
}