二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

code

int binarySearch (int arr[],int length,int target) {
    int start = 0;
    int end = length - 1;
    while (start <= end) {
        int mid = (start + end)/2;
        if (target == arr[mid]) {
            return arr[mid];
        } else if (target > arr[mid]) {
            start = mid + 1;
        } else {
            end = mid -1;
        }
    }
    return -1000;
}


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int arr[] = { 1,3,6,7,11};
        int length = (int) sizeof(arr) / sizeof(*arr);
        int k = binarySearch(arr,length,7);
        printf("%d ", k);
        
    }
    return 0;
}

时间复杂度分析

while循环里面的代码是和数组长度无关的常数操作，所以层高k代表的就是时间复杂度k=,所以时间复杂度为O()