查找算法007-二分查找


说明:元素必须是有序的,如果是无序的则要先进行排序操作。


1、算法思想:

二分查找(又称为折半查找)是在有序序列中查找比较多的查找算法。

基本思路:设有一个从小到大的序列,取中间的元素m进行比较,如果等于需要查找的元素x则返回元素m的下标,若x大于m则再从右边的区间查找,若x小于m则再从左边的区间查找,这样每次减少一半的查找范围。时间复杂度为O(lgn),查找速度相对顺序查找要快很多,但是查找的数据序列必须是有序序列(即数据是从小到大或从大到小排序的)。


2、时间复杂度:O(lgn)


3、C++ 实现:

#include<stdio.h>

/* 二分查找算法 
   a为数据数组,len为数组a的长度,x为查找的元素 
   如果查找成功返回元素x在数组a中的下标,找不到则返回-1 
 */ 
int binarySearch(int a[],int len, int x)
{
    int mid;          // 中间下标
    int low=0;        // 区间的左端下标
    int high=len-1;   // 区间的右端下标
    
    while(low <= high)
    {
        mid = low + (high-low)/2;  // 计算中间下标, 若使用(low+high)/2可能会有整数溢出:当low和high的值较大时(接近整型数所能表示的范围),low+high的值就会溢出
        if(x==a[mid])
            return mid;    // 若找到返回元素的下标 
        else if(x>a[mid])
            low=mid+1;     // 在右半边区间搜索 
        else
            high=mid-1;    // 在左半边区间搜索 
    }
    return -1;   // 没有找到 
}

int main()
{
    int a[10]={0,1,2,3,4,5,6,7,8,9}; // 必须是有序序列 
    int x=7;   // 需要查找的元素
    int i = binarySearch(a, 10, x);
    if(i!=-1)
        printf("元素%d在第%d个位置\n",x,i+1);
    else
        printf("没有找到元素:%d\n",x);
    return 0;
}


happysneaker.com

运行结果

Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论