欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找算法的实现

程序员文章站 2024-03-20 09:49:58
...

二分查找又称折半查找,时间复杂度为logn,效率比较高。

算法思想:

二分查找算法是对于一个有序序列而言的,假设这个序列是升序排列的,那么在查找元素时,首先与序列中的中间值进行比较,如果大于中间值,就从中间值的右边找,如果小于中间值,就从中间值的左边找,直到扎到该元素,或者所查找的序列为空时。

代码示例如下:

#include <stdio.h>
#include <assert.h>

int Search(int *arr,int len,int value)
{
    assert(arr!=NULL);
    int left=0;//查找范围的最小值
    int right=len-1;//查找范围的最大值
    int mid;


    while(left<=right)
    {
        mid = (left + right)/2;//查找范围的中间值
        if(arr[mid]<value)//如果要找的值大于中间值,就在右半部分进行查找
        {
            left = mid+1;//右半部分进行查找
        }
        else if(arr[mid]>value)
        {
            right = mid;//左半部分进行查找
        }
        else
        {
            return right;
        }
    }

    return -1;
}