查找算法：折半查找算法实现及分析

男娘i 2022-05-29 22:46 283阅读 0赞

# 折半查找算法介绍 #

**折半查找（Binary Search）又称为二分查找**。**它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储**。从算法名称可以看出算法的思路，先取有序序列中间值与查找值进行比较，中间值小于查找值 就查找后一子表，如果中间值大于查找值 就查前移子表，直到查找到或者子表不存在为止。由于折半查找的查找范围是成倍的缩写，所以**折半查找法的算法时间复杂度为logn。**

# 折半查找算法代码 #

代码简单哟，**因为我们并不知道循环次数，所以优先采用的while 循环**，当然**for、while、do while 循环都可以相互转换的哈**。

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    //折半查找法 arr数组，length 数组长度，key 查找的关键字
    //返回查找值的下标 ，没查找到 返回-1
    int Binary_Search(int *arr, int length, int key)
    {
    	int low = 0;//低位下标
    	int high = length-1;//高位下标
    	int mid;//中间值下标
    	while (low <= high)
    	{
    		mid = (low + high) / 2;
    		if (key < arr[mid])
    		{
    			high = mid - 1;
    		}
    		else if(key > arr[mid])
    		{
    			low = mid + 1;
    		}
    		else
    		{
    			return mid;
    		}
    	}
    	return -1;
    }
    int main(int argc, char *argv[])
    {
    	int arr[10] = { 0,1,2,3,4,5,6,7,8,9};
    	int index1 = Binary_Search(arr, 10, 5);
    	int index2 = Binary_Search(arr, 10, 100);
    	printf("index1 = %d，index2 = %d\n",index1,index2);
    	return 0;
    }

# 运行结果检测 #

![20180227194142352][]

[20180227194142352]: /images/20220530/6297904328ca4d469739b82bc97b9441.png