对于长度为n的线性表，若采用顺序查找法进行查找，则时间复杂度

[问答题]

对于长度为n的线性表，若采用顺序查找法进行查找，则时间复杂度为（）；若采用折半查找法进行了查找，则时间复杂度为（）。

杨😗

O(n);

O(log2n)

发表于 2020-04-29 23:57:02 回复(0)

张小头

顺序查找法的时间复杂度为O(n)，二分查找法为树的深度，时间复杂度为O(log2n)

//
// Created by John on 2021/02/21.
//二分查找
//注意数组一定要有序才能用
//

template<class T,class F>
int binarySearch(T& L,F key){
    int low = 0,high = sizeof(L)/sizeof(L[0]) - 1,mid;
    while(low <= high){
        mid = (low + high)/2;
        if (L[mid] == key) return mid; //返回查找成功的位置
        else if (L[mid] > key) high = mid - 1; //从前半部分查找
        else low = mid + 1; //从后半部分查找
    }
    return -1; //查找失败，返回-1
}

发表于 2021-02-21 17:25:53 回复(0)