c语言数据结构二分查找算法

梦里梦外; 2022-01-23 12:51 265阅读 0赞

/\*  
\*二分查找算法(对已经排好序的数据而言)  
\*设置一个 L M H 三个临时变量 将排好序的数组  
\*分别对应 第一个元素的下标 和中间元素的下标 和最后元素的下标  
\*首先将数组进行排序  
\*假如第一次元素和对应的M所在数组中的元素进行比较的时候  
\*小于中间元素的值 将H的值调整到M-1  
\*反过来将L的对应的数组的下标调整到M+1处  
\*降低时间复杂度  
\*对数组的二分算法  
\*/

#include<stdio.h>
    #include<stdlib.h>
    int Binary_search(int *s,int length,int key);//二分查找函数
    void sort(int *s,int length);//对数组进行排序函数
    void main()
    {
        int m;
        int i;
        int key;
        int n[100];//待排序数组
        printf("请输入数据的个数:\n");
         scanf("%d",&m);
          printf("请依次输入数据:\n");
             for(i=0;i<m;i++)
             {
                 scanf("%d",&n[i]);
             }
             sort(n,m);
             printf("数据递增排序的效果为:\n");
               for(i=0;i<m;i++)
                  printf("%d\t",n[i]);
               printf("\n");
             printf("请输入要查找的数据:\n");
             while(scanf("%d",&key)!=EOF)
             {
                 int pos=Binary_search(n,m,key);
               if(pos==-1)
                printf("没有找到需要查询的数据:\n");
                 else
                    printf("数据 %d->位置 %d\n",key,pos);
             }
    
    }
    void sort(int *s,int length)//对数组进行排序函数
    {
        //改进版的冒泡排序算法 递增排序
          int i=length-1;//比较的次数
          int j;
          int  t;
          int flag;
          while(flag)
          {
              flag=0;
              for(j=0;j<i;j++)
              {
                  if(s[j]>s[j+1])
                  {
                      t=s[j];
                      s[j]=s[j+1];
                      s[j+1]=t;//交换数据
                      flag=1;
                  }
    
    
              }
              i--;
    
          }
    }
    int Binary_search(int *s,int length,int key)//二分查找函数
    {
        int L,H,M;
        L=0;
        H=length-1;
    
        while(L<=H)
        {
            M=(L+H)/2;
            if(s[M]==key)
            {
                return M;
            }
            if(key<s[M])
            {
                H=M-1;
            }
            else
            {
                L=M+1;
            }
    
        }
             return  -1;
    }