C语言：通过函数实现一个整形有序数组的二分查找

 

一、解析：

1、定义：

        二分查找法实质上是不断地将有序数据集(表中元素是升序排列)进行对半分割，并检查每个分区的中间元素。此过程的实施是通过变量left和right控制一个循环来查找元素（其中left和right是正在查找的数据集的两个边界值）。

2、思路：

         2.1、首先，将left设置为0、将right设置为size-1。在循环的每次迭代过程中，将mid设置为(left+right)/2。将表中间位置记录的关键字与查找关键字比较，如果两者相等，则返回关键字，显示查找成功。

	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };

	int sz = sizeof(arr) / sizeof(arr[0]);

	int k = 7;

    int left = 0;
    int right = sz-1;

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

         2.2、否则通过中间位置记录的关键字将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一个子表，否则进一步查找后一个子表：

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;//找不到

        （1）.如果处于mid的元素比关键字值小，将变量left移动到mid后的一个元素的位置上。因此下一组要搜索的区域是当前数据集的后一个子表。

        （2）.如果处于mid的元素比关键字值大，将变量right移动到mid前一个元素的位置上。因此下一组要搜索的区域是当前数据集的前一个子表。

        （3）.随着搜索的不断进行，left从左向右移，right从右向左移。一旦在mid处找到目标，查找将停止，如果没有找到目标，left向右移动和right向左移动。

        2.3、重复以上过程，直到找到满足条件的关键字，使查找成功。当left>right时，此时查找不成功。

	int ret = binary_search(arr, k, sz);

	if (-1 == ret)
		printf("找不到\n");
	else
		printf("找到了，下标是:%d\n", ret);
    
    return 0;

二、总代码：

#include<stdio.h>
//int binary_search(int* arr, int k, int sz)
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;//找不到
}

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

	int k = 7;

	//找到了返回下标，0~9
	//找不到返回 -1

	int ret = binary_search(arr, k, sz);

	if (-1 == ret)
		printf("找不到\n");
	else
		printf("找到了，下标是:%d\n", ret);

	return 0;
}