二分查找法c语言实现

本是古典何须时尚 2021-10-13 16:51 316阅读 0赞

二分查找法是从已经排序的线性表（通常是数组）里快速查找到目标元素所在索引，时间复杂度O(log2n)。

以下是从java源代码中抄来，稍微修改的代码。

#include <stdio.h>
    #include <assert.h>
    
    #define ARRAY_SIZE(x) (sizeof(x)/sizeof((x)[0]))
    
    int binarySearch(const int[], size_t,const int);
    
    void rangeCheck(size_t, size_t, size_t);
    
    int binarySearch0(const int[], size_t fromIndex, size_t toIndex, const int);
    
    int main()
    {
        int array[] = {
        1, 3, 5, 7, 9};
        int key = 3;
        int result = binarySearch(array, ARRAY_SIZE(array),key);
    
        if( result == -1)
            printf("Element %d is not present in array\n",key);
        else
            printf("Element %d is present at index %d\n", 
                                key,result); 
    
        
        return 0;
    }
    
    int binarySearch(const int array[], size_t size,const int key)
    {
        return binarySearch0(array,0, size,key);
    }
    
    void rangeCheck(size_t arrayLength , size_t fromIndex, size_t toIndex)
    {
        assert(fromIndex > toIndex);
        assert(fromIndex < 0);
        assert(toIndex > arrayLength);
    }
    //函数指针()
    int binarySearch0(const int array[], size_t fromIndex, size_t toIndex, const int key)
    {
        int low = fromIndex;
        int high = toIndex - 1;
        while (low <= high) {
            int mid = (low + high) >> 1; //算法精妙之处,用位移方法快速决定中值的索引 int midVal = array[mid];        
                int cmp = midVal - key;
            
            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
            return -(low + 1);  // key not found.
        return 0;
    }

运行结果:

Element 3 is present at index 1

转载于:https://www.cnblogs.com/passedbylove/p/11255192.html