数组二分查找算法的C语言实现

如果您对这篇文章有任何建议的话，欢迎在评论区留言！

如果您认为我写的还不错的话，可以考虑打赏哦！

二分查找算法简介

在计算机科学中，二分查找算法（英语：binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm）、对数搜索算法（英语：logarithmic search algorithm），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找算法使用常数空间，对于任何大小的输入数据，算法使用的空间都是一样的。除非输入数据数量很少，否则二分查找算法比线性搜索更快，但数组必须事先被排序。尽管一些特定的、为了快速搜索而设计的数据结构更有效（比如哈希表），二分查找算法应用面更广。

二分查找算法简图

二分查找算法的步骤

设有有序（这里为升序）数组（这里以int整型数组为例），我们要查找一个元素key。

int a[10] = {1,3,7,11,20,23,27,28,31,38};

int key = 27;

数组的第一个元素是a[0]，最后一个元素是a[9]。于是我们定义最左侧为0，最右侧为9。

int left = 0, right = 9;

我们需要将数组二分。为了避免之后的二分步骤中出现溢出数组范围的情况，我们以如下方式定义mid.

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

检查a[mid]是否与key相等。若相等，直接返回mid。若不相等，则根据key和a[mid]的关系更新left和right，然后重复执行步骤3、4，直至mid与key相等或left>right。
if (a[mid] < key)
{
left = mid + 1;
}
else if (a[mid] > key)
{
right = mid - 1;
}
else
{
return mid;
}

C语言实现

Tips: 这部分代码可以直接复制，以备重用

通过循环实现

//函数功能：二分查找
//函数参数：分别为被查找的数组，数组长度，所查找的元素
//函数返回值：如果找到，则返回该元素在数组中的下标，否则返回-1 
int BinarySearch(int a[], int n, int key); 

int BinarySearch(int a[],int n,int key)
{
    int left = 0, right = n - 1;
    while (left<=right)
	{
		int mid = left + (right - left) / 2;

		if (a[mid] < key)
		{
			left = mid + 1;
		}
		else if (a[mid] > key)
		{
			right = mid - 1;
		}
		else
		{
            return mid;
        }
	}
	return -1;
}

通过递归实现

/*
函数功能：二分查找
函数参数：分别为被查找的数组，所查找的元素，查找范围的左侧、右侧
函数返回值：如果找到，则返回该元素在数组中的下标，否则返回-1 
*/
int RecurBinarySearch( int a[], int key, int left, int right);

int RecurBinarySearch( int a[] , int key , int left , int right )
{
    int mid = left + (right - left) / 2;
    if (left>right)
    {
        return -1;
    }
    else if (a[mid]<key)
    {
        return RecurBinarySearch(a, key, mid + 1, right);
    }
    else if (a[mid]>key)
    {
        return RecurBinarySearch(a, key, left, mid - 1);
    }
    else
    {
        return mid;
    }
}

测试程序

通过循环实现

#include <stdio.h>

//函数功能：二分查找
//函数参数：分别为被查找的数组，数组长度，所查找的元素
//函数返回值：如果找到，则返回该元素在数组中的下标，否则返回-1 
int BinarySearch(int a[],int n,int key) ; 

int main()
{
    int    num[200000] ; 
    int        n , m, i;    
    int        key ;
    
    scanf("%d%d",&n,&m); 
    for( i = 0 ; i < n ; i++ ) 
        scanf("%d",&num[i]) ;
        
    for( i = 0 ; i < m ; i++ ) 
    {
        scanf("%d",&key) ;
        printf("%d",BinarySearch(num,n,key)) ;
        if ( i != m - 1 ) printf(" ") ;
        else printf("\n") ;
    }
    return 0 ;
}

int BinarySearch(int a[],int n,int key)
{
    int left = 0, right = n - 1;
    while (left<=right)
	{
		int mid = left + (right - left) / 2;

		if (a[mid] < key)
		{
			left = mid + 1;
		}
		else if (a[mid] > key)
		{
			right = mid - 1;
		}
		else
		{
            return mid;
        }
	}
	return -1;
}

测试结果：

输入样例：

15
20
-293 -213 -23 0 1 5 11 23 56 67 87 273 999 2132 10000
-23 -99999 0 999 953 67 56 44 33 87 -293 23 11 273 -213 2132 10000 87654 1 5

输出样例：

2 -1 3 12 -1 9 8 -1 -1 10 0 7 6 11 1 13 14 -1 4 5

通过递归实现

#include<stdio.h>

#define MAXN 200000

int RecurBinarySearch( int a[] , int key , int left , int right ) ;

int main()
{
    int        a[MAXN];
    int        n , m , i , key ;
    
    scanf("%d %d",&n , &m );    
    for( i = 0 ; i < n ; i++ )
        scanf("%d", &a[i]);
        
    for( i =0 ; i < m ; i++ )
    {
        scanf("%d",&key);
        printf( "%d" , RecurBinarySearch( a , key , 0 , n - 1 ) );
        if ( i != m - 1 ) printf(" ") ;
        else printf("\n") ; 
    }

    return 0;
}

int RecurBinarySearch( int a[] , int key , int left , int right )
{
    int mid = left + (right - left) / 2;
    if (left>right)
    {
        return -1;
    }
    else if (a[mid]<key)
    {
        return RecurBinarySearch(a, key, mid + 1, right);
    }
    else if (a[mid]>key)
    {
        return RecurBinarySearch(a, key, left, mid - 1);
    }
    else
    {
        return mid;
    }
}

测试结果：

输入样例：

15 
20
-293 -213 -23 0 1 5 11 23 56 67 87 273 999 2132 10000
-23 -99999 0 999 953 67 56 44 33 87 -293 23 11 273 -213 2132 10000 87654 1 5

输出样例：

2 -1 3 12 -1 9 8 -1 -1 10 0 7 6 11 1 13 14 -1 4 5