題目：

寫一個函數(shù)，實現(xiàn)一個整型有序數(shù)組的二分查找，找出要找的數(shù)字在數(shù)組中對應的下標。

? ? ? ? ? ? ? ? ? ??

?=========================================================================

? ? ? ? ? ? ? ? ? ? ? ?

思路：

總體思路：

（一）自定義函數(shù)部分：

? ? ? ? ? ? ? ??

（1）.

參數(shù)：

int arr[] --?數(shù)組首地址

?int k -- 要在數(shù)組中找的數(shù)字

?int sz -- 數(shù)組長度

? ? ? ? ? ? ??

定義左右下標；

? ? ? ? ? ? ? ? ? ?

（2）.

使用二分查找法；

? ? ? ? ? ? ? ?

（二）主函數(shù)部分：

? ? ? ? ? ?

定義有序數(shù)組，設置要查找的值，求出數(shù)組元素個數(shù)。

? ? ? ? ? ? ? ?

調(diào)用自定義函數(shù)。

? ? ? ? ? ? ? ?

判斷自定義函數(shù)的返回值，打印相應的情況。

? ? ? ? ? ? ? ??

---

? ? ? ? ? ? ? ? ?

自定義函數(shù)部分：

第一步：

（1）. 形參的設置：

int arr[] -- 數(shù)組首地址；

int k -- 要在數(shù)組中找的數(shù)字；

int sz -- 數(shù)組長度。

? ? ? ? ? ? ?

（2）. 定義左右下標 -- left 和 right

? ? ? ? ? ? ? ? ? ? ?

實現(xiàn)代碼：

#include <stdio.h>

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


}

int main()
{

	return 0;
}

實現(xiàn)圖片：

? ? ? ? ? ? ? ? ?

---

? ? ? ? ? ? ? ? ?

第二步：

使用二分查找方法：

? ? ? ? ?

（1）. 使用while循環(huán)。

? ? ? ? ??

（2）. 生成中間值下標 mid ：

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

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

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

這時 兩邊是一樣的，任意一邊都是平均值（中間值）

? ? ? ? ? ? ??

（3）.

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

舍棄中間值和中間值左邊的所有數(shù)，調(diào)整 左下標left ：left = mid + 1。

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

舍棄中間值和中間值右邊的所有數(shù)，調(diào)整 右下標right ：right = mid -?1。

如果中間值 等于?要找的值，

返回中間值下標mid。

? ? ? ? ? ? ? ?

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

? ? ? ? ? ? ? ? ? ? ?

實現(xiàn)代碼：

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

	//使用while循環(huán)
	while (left <= right)
	{
		//生成中間值下標 mid ：
		int mid = left + (right - left) / 2;

		//二分查找:
		if (arr[mid] < k)//中間值 小于 要找的值
		{
			left = mid + 1;
			//舍棄中間值和中間值左邊的所有數(shù)，
			//調(diào)整 左下標left ：left = mid + 1。
		}
		else if (arr[mid] > k)//中間值 大于 要找的值
		{
			right = mid - 1;
			//舍棄中間值和中間值右邊的所有數(shù)，
			//調(diào)整 右下標right ：right = mid -?1。
		}
		else if (arr[mid] == k)//中間值 等于?要找的值
		{
			return mid;
			//返回中間值下標mid。
		}
	} 
	if (left > right)
	{
		return -1; //找不到則返回-1
	}
}

實現(xiàn)圖片：

? ? ? ? ? ? ? ? ?

---

? ? ? ? ? ? ? ? ?

主函數(shù)部分：

（1）. 定義有序數(shù)組，設置要查找的值，求出數(shù)組元素個數(shù)。

? ? ? ? ? ? ? ?

（2）. 調(diào)用自定義函數(shù)。

? ? ? ? ? ? ? ??

（3）. 判斷自定義函數(shù)的返回值，打印相應的情況。

? ? ? ? ? ? ? ? ? ? ?

實現(xiàn)代碼：

#include <stdio.h>

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

	//使用while循環(huán)
	while (left <= right)
	{
		//生成中間值下標 mid ：
		int mid = left + (right - left) / 2;

		//二分查找:
		if (arr[mid] < k)//中間值 小于 要找的值
		{
			left = mid + 1;
			//舍棄中間值和中間值左邊的所有數(shù)，
			//調(diào)整 左下標left ：left = mid + 1。
		}
		else if (arr[mid] > k)//中間值 大于 要找的值
		{
			right = mid - 1;
			//舍棄中間值和中間值右邊的所有數(shù)，
			//調(diào)整 右下標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 }; //定義有序數(shù)組
	int k = 7; //設置要查找的值
	int sz = sizeof(arr) / sizeof(arr[0]); //求出數(shù)組元素個數(shù)
	// 整個數(shù)組大小 / 單個數(shù)組元素大小 = 數(shù)組元素個數(shù)

	//調(diào)用自定義函數(shù)：
	int ret = binary_search(arr, k, sz); //ret接收返回的下標

	//判斷自定義函數(shù)的返回值，打印相應的情況：
	if (ret == -1) //未找到，返回-1
	{
		printf("找不到\n");
	}
	else
	{
		printf("找到了，下標是：%d\n", ret);
	}

	return 0;
}

實現(xiàn)圖片：

? ? ? ? ? ? ? ? ? ??

最終代碼和實現(xiàn)效果

最終代碼：

#include <stdio.h>

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

	//使用while循環(huán)
	while (left <= right)
	{
		//生成中間值下標 mid ：
		int mid = left + (right - left) / 2;

		//二分查找:
		if (arr[mid] < k)//中間值 小于 要找的值
		{
			left = mid + 1;
			//舍棄中間值和中間值左邊的所有數(shù)，
			//調(diào)整 左下標left ：left = mid + 1。
		}
		else if (arr[mid] > k)//中間值 大于 要找的值
		{
			right = mid - 1;
			//舍棄中間值和中間值右邊的所有數(shù)，
			//調(diào)整 右下標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 }; //定義有序數(shù)組
	int k = 7; //設置要查找的值
	int sz = sizeof(arr) / sizeof(arr[0]); //求出數(shù)組元素個數(shù)
	// 整個數(shù)組大小 / 單個數(shù)組元素大小 = 數(shù)組元素個數(shù)

	//調(diào)用自定義函數(shù)：
	int ret = binary_search(arr, k, sz); //ret接收返回的下標

	//判斷自定義函數(shù)的返回值，打印相應的情況：
	if (ret == -1) //未找到，返回-1
	{
		printf("找不到\n");
	}
	else
	{
		printf("找到了，下標是：%d\n", ret);
	}

	return 0;
}

實現(xiàn)效果：

文章來源地址http://www.zghlxwxcb.cn/news/detail-481979.html

到了這里，關(guān)于C語言：寫一個函數(shù)，實現(xiàn)一個整型有序數(shù)組的二分查找的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！