数据结构--杂记-二分查找

古城微笑少年丶 2022-06-07 03:57 174阅读 0赞

*  介绍二分查找之前，首先看看简单的数值比较的两种实现；
    
     *  数值比较是简单的`if-else-if`语句的使用，先看看函数版本的实现:
    
        int compare(int a,int b){
            if(x<y) return -1;
            else if(x==y)return 0;
            else return 1;
        }
    
     *  上面的程序在处理`int`类型的数据，进行比较大小是没有错误的，在绝大多数情况下是可以运行的；
     *  数值比较的宏实现方式；
    
        ＃define COMPARE(x,y) (((x)<(y)) ? -1 :((x)==(y)) ? 0:1)
    
     *  使用宏实现的大小比较，在处理`float`,`double`的数值时是有点小问题的；
     *  浮点数在计算机的存储和整形的存储是不太一样的，对于小数点后面的数字每一位分别表示`1/2,1/4,1/8,1/16`,浮点数的存储实际上采用的是微分的思想，也就是在无限进行数值的逼近，对于绝大多数浮点数都是可以准确进行存储并且进行比较的；
     *  `float`浮点数在进行存储过程中的一个程序验证；

int main(){
        float lk=2.424523525566476667;
        printf("%f\n",lk);  
    
        double llk=2.42452352556647667;
        printf("%f\n",llk);
    }

*  输出结果是:  
    ![这里写图片描述][SouthEast]
 *  在进行浮点数的保存和输出过程中，其实是进行了四射五入的，当然不同的编译器对于这个处理也是不同的，这只是数值存储的一种情况，特殊的在整理之后再发；
    
     *  为了防止特殊情况的发生，浮点数的比较应该采用阀值的思想来进行相等性的比较；

//这里是用compare变量来允许用户在进行浮点数的比较时，可以传入一个阀值来判断两个浮点数是否相等;
    
    int compare(float a,float b,float compare)
    {
        if(a<b) return -1;
    //fabs()如果是浮点数绝对值函数使用fabs()，如果是整型使用函数abs()；
        else if(fabs(a-b)<compare) return 0;
        else return 1;
    }

*  分析二分查找算法执行过程：
    
     *  1.首先函数原型需要传递的参数包括：`array[]`,`searchnum`,`left`,`right`,四个参数的意思分别是查找的有序数组，需要查找数值，查找的左边界，查找的右边界；
     *  2.对于查找的过程包括三种情况：  
        
        
         *  1.`searchnum<array[middle]`:就应该在有序数组的左边进行查找，需要改变`right`的值：`right=middle-1`；
         *  2.`searchnum==array[middle]`找到的数据就是需要的数据，那么直接进行返回：`return middel;`
         *  3.`searchnum>array[middle]`：说明查找的数值应该在数值的右半本部分，所以应该改变`left=middle+1`；
 *  `Binary_search()`的实现：

#include <stdlib.h>
    #include <stdio.h>
    #include "Mystd.h"
    int Compare(int left, int right, int compare)
    {
        if (left < right) return -1;
        else if (abs(left - right) < compare) return 0;
        else return 1;
    }
    
    int Binary_search(int array[], int SearchNumber, int left, int right)
    {
        if (array == NULL || left == right)
            exit;
        int middle = 0;
        while (left <= right)
        {
            middle = (left + right) / 2;
            switch (Compare(array[middle], SearchNumber, 1))
            {
            case -1:
                left = middle + 1;
                break;
            case 0:
                return middle;
            case 1:
                right = middle - 1;
            }
    
        }
        return -1;
    
    }
    
    int main()
    {
        int myarray[] = {
       1, 6, 9, 0, 3, 6, 5,3, 1, 7, 6, 9, 4};
        choice_sort(myarray,sizeof(myarray)/sizeof(int));
        size_t i=0;
        for( i=0;i<sizeof(myarray)/sizeof(int);++i)
            printf("%d ",myarray[i]);
        printf("\n");
    
        int k = Binary_search(myarray,3,0,sizeof(myarray)/sizeof(int));
        if(k==-1)
            printf("Not found!!");
        else
            printf("Found it at: %d \n",k);
    
         k = Binary_search(myarray,3,0,k);
        if(k==-1)
            printf("Not found!!");
        else
            printf("Found it at: %d \n",k);
    }

*  程序的执行结果  
    ![这里写图片描述][SouthEast 1]
 *  `Binary_Search`对于没有重复元素的查找是没有丝毫问题的，这里尝试处理的的是具有重复元素的查找过程；
 *  由执行结果看一个看出,程序首先找出了最右边的`3`位置是４，然后再修正之后，才找到了左边的三，如果在修正过程中发生错误，那么左边的`3`很有可能找不到；
 *  来看看这种情况是如何发生的:  
    ![这里写图片描述][SouthEast 2]
 *  对于这个这种情况可以使用`C++STL`来进行尝试;

int main(){
        vector<int>  myarry={
       1,6,9,0,3,6,5,3,1,7,9,4};
        sort(myarry.begin(),myarry.end());
        auto it =binary_search(myarry.begin(),myarry.end(),3);
        if(it==0)
            cout << "Not found\n";
        else
            cout << "Find position: " << it << endl;
    }

＊使用`C++STL`提供的`Binary_search`仅仅可以查看是否有这个元素，如果需要得到元素的位置还需要这样;

int main()
    {
        vector<int>  mytins = {
       1, 6, 9, 0, 3, 6, 5, 3, 1, 7, 9, 4};
        pair<vector<int>::iterator, vector<int>::iterator> bounds;
    
        sort(mytins.begin(), mytins.end());
        bounds = equal_range(mytins.begin(), mytins.end(), 3);
        cout << "bounds at positions " << (bounds.first - mytins.begin());
        cout << " and " << (bounds.second - mytins.begin()) << endl;
    }

*  代码的执行结果是:  
    ![这里写图片描述][SouthEast 3]
 *  这种方式的查找对于两个重复元素的查找是比较有效的,对于更多的重复元素还需要进行实验，在总结之后在整理;
 *  对于二分查找时间复杂度是`log2 n`，查找元素还是很快速的;

[SouthEast]: /images/20220607/8db8ba25370e4bef9d54826c021d458a.png
[SouthEast 1]: /images/20220607/52e3ed41c496408e8b9847435c2b978b.png
[SouthEast 2]: /images/20220607/ab13ce705d804945a3be65c7ec6e1edb.png
[SouthEast 3]: /images/20220607/bd689772fe2c4839a5cf35f1cf459b50.png