元素的查找-二分法

元素查找

• 静态查找：元素是记录固定的，只有查找，无其它操作。
• 动态查找：数据记录的是动态变化的，除了查找，还可以删除，增加操作。

静态查找：
方法一 ：对于未排序的数据——顺序查找
方法二：排好次序的数据———二分法查找

---

方法二 ： 二分法查找

1. 比起顺序查找法来说二分法非常快
2. 顺序查找法时间复杂度为O(n),二分法时间复杂度O(logN)。

3. 运用前提：元素必须有序排列，即必须预先有序化处理。

   1. 思路：

    (1)将数据有序化存储在数组中tb；
    (2)设临时变量left,right,mid,NotFound=-1；
    (3)初始化left为1，right为tb数组的length。
    (4) left<mid<right, mid=(left+right)/2，向下取整。
    (5)开始循环遍历，循环条件是left<=right；
    (6)查找k值:
    若k<mid，k在查找范围左边：则left不变,right=mid-1,求出mid；
    若mid<k，k在查找范围右边：则right不变,left=mid+1,求出mid；
    若k=mid,能找到k在该数组tb中,返回该位置mid。
    (7)当left>right，结束循环，未能找到k,返回NotFound。
   具体思路，如下图例所示：
   

   情况一：查找44
   
   情况二：查找202
   
   情况三：查找226
   

   2. 代码：

#include<stdio.h>
#include<stdlib.h>

/*遍历查询*/
int BinarySearch(int tb[],int length,int k){
    int left,right,mid,NotFound=-1;
    left=0;
    right=length;
    while(left<=right){
        mid=(left+right)/2;
        if(k<tb[mid]){//在k前半段
            right=mid-1;
        }
        else if(k>tb[mid]){//在k后半段
            left=mid+1;
        }
        else{//k==tb[mid]找到元素
            return mid;
        }
    }
    //循环完毕还未找到
    return NotFound;
}

/*主函数*/
int main(){
    int k,result;
    int arr[13]={5,16,39,45,51,98,100,202,226,321,368,444,501};
    printf("请输入一个你想查询的数据,探索是否存在隐秘的数组中：\n");
    scanf("%d",&k);
    result=BinarySearch(arr,13,k);
    printf("\n%d",result);
    printf("\n");
    return 0;
}

3 .运行截图：

情况一，寻找 44这个值，没找到：

情况二，寻找 202 这个值，找到了，并返回序号：

情况三，寻找 226这个值，找到了，并返回序号：