二分查找算法（折半查找算法）

一般当我们在一组有序数组中查找某个元素n时，我们可以使用逐个对比查找的方法

例如

#include <stdio.h>

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10};
	int i = 0;
	int k = 6;
	int sz = sizeof(arr) / sizeof(arr[0]);   //计算元素个数
	for (i = 0; i < sz; i++)
	{
		if (k == arr[i])
		{
			printf("该数即为所求,下标为:%d
", i);
			break;
		}
	}
	if (i == sz)
		printf("所给出的数中没有该数
");
	return 0;
}

但是对于这种方法来讲一般比较麻烦，因为对于一个含有n个元素的数组，将会查找n次

因此我们引进二分查找算法来计算

同样的道理，我们在1~10这些数中寻找6

这样就大大省略了查找时间，才开始的10次查找——>3次

二分查找算法的源代码一般为：

int arr[]={ };  //空里面即为所给的元素
int k=?；    //为所求的数
int sz=sizeof(arr)/sizeof(arr[0]);    //计算元素个数
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
    {
        printf("即为所求");
        break;
    }
    if(left>right)
        printf("所给的元素里面没有该数
");
}

下面我们给出具体的题目：在1~10这些有序数里面，寻找6；

思路为

代码展示如下：

#include <stdio.h>

int main() {
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };  //空里面即为所给的元素
    int k = 6;
    int sz = sizeof(arr) / sizeof(arr[0]);    //计算元素个数
    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
        {
            printf("即为所求的数，下标为：%d
",mid);
            break;
        }
        if (left > right)
        {
            printf("所给的元素里面没有该数
");
        }
    }
}