二分法查找 订阅
算法:二分法查找适用于数据量较大时,但是数据需要先排好顺序。主要思想是:(设查找的数组区间为array[low, high])(1)确定该区间的中间位置K(2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。区域确定如下:a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……,K-1]b.array[k] 展开全文
算法:二分法查找适用于数据量较大时,但是数据需要先排好顺序。主要思想是:(设查找的数组区间为array[low, high])(1)确定该区间的中间位置K(2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。区域确定如下:a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……,K-1]b.array[k]
信息
外文名
Binary Search
要    求
查找算法
中文名
二分法查找
主要思想
数组中元素是有顺序的
二分法查找算法
[一维数组,折半查找]假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2.1.开始令front=0(指向3),end=7(指向88),则mid=3(指向36)。因为a[mid]>x,故应在前半段中查找。2.令新的end=mid-1=2,而front=0不变,则新的mid=1。此时x>a[mid],故确定应在后半段中查找。3.令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a[mid]=x,查找成功。如果要查找的数不是数列中的数,例如x=25,当第三次判断时,x>a[mid],按以上规律,令front=mid+1,即front=3,出现front>end的情况,表示查找不成功。例:在有序的有N个元素的数组中查找用户输进去的数据x。算法如下:1.确定查找范围front=0,end=N-1,计算中项mid=(front+end)/2。2.若a[mid]=x或front>=end,则结束查找;否则,向下继续。3.若a[mid]x,说明待查找的元素值只可能在比中项元素小的范围内,则把mid-1的值赋给end,并重新计算mid,转去执行步骤2。
收起全文
精华内容
下载资源
问答
  • 二分法查找

    2016-11-21 11:10:39
    二分法查找
    #include<stdio.h>
    #include<malloc.h>
    #include <stdlib.h>
    #define max 20
    
    typedef struct {
        int  data[max];
        int last;
    }SequenList;
    
    
    SequenList * init();                        //  新建顺序表并初始化
    int search(SequenList * ,int  );            //  二分法查找
    void show(SequenList *);                    //展示元素
    
    int main (){
        SequenList * head = init();
        show(head);
        int key ;
        int s ;
        while(1){
        fflush(stdin);
        scanf("%d",&s);
        key = search(head,s);
        if (key >= 0 ){
            printf("该元素的位置是: %d \n",key+1);
        }else{
            printf("\n找不到该元素\n");
        }
        }
        system("pause");
        return 0;
    }
    
    SequenList * init(){
        SequenList * p = (SequenList*)malloc(sizeof(SequenList));
        p ->last = 0;
        int i = 0;
        p->data[0] = rand()%10;
        for (i = 1 ; i < 10 ; i ++ ){
            p->data[i] = p->data[i-1]+ rand()%10;
            p->last++;
        }
        return p;
    }
    
    int search(SequenList *  p , int key ){
        int low ,middle,high ;
        low = 0;
        high = p->last;
        middle = (low+high)/2;
        while (low <= high){
            if (key > p->data[middle]){
                low = middle+1;
            }
            else if (key < p->data[middle]){
                high = middle-1;
            }else{
                return middle;
            }
            middle = (low+high)/2;
        }
        return -1;
    }
    void show(SequenList * p ){
        int i = 0 ;
        for (i = 0 ; i < p->last ; i ++){
            printf("%d ",p->data[i]);
        }
        printf("\n");
    }

    运行结果如下

    这里写图片描述

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,517
精华内容 3,006
关键字:

二分法查找