欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

折半查找法

程序员文章站 2024-03-20 18:24:52
...
/**  
     * 折半查找又称二分查找,算法复杂度为O(log(n)),但缺点是要求  
     * 待查表为有序表,此算法充分利用了数组的有序性,采用分治策略  
     * 找出待查元素在数组中的位置,若数组中不存在该元素,则返回-1  
     */    
        
    #include <stdio.h>    
        
    int binary_search(int array[], int n, int data)    
    {    
        int low = 0, high = n - 1, mid;    
        
        while(high >= low)    
        {    
            mid = (low + high) / 2;    
        
            if(array[mid] == data)    
                return mid;    
            else if(array[mid] > data)    
                high = mid - 1;    
            else    
                low = mid + 1;    
        }    
        return -1;    
    }    
        
    main()    
    {    
        int array[] = {1, 5, 30, 41, 100, 101};    
        printf("%d\n", binary_search(array, 6, 101));    
        printf("%d\n", binary_search(array, 6, 2));    
    }    
        
    运行结果:    
    5    
    -1

转载于:https://my.oschina.net/u/1012872/blog/127146