1. 折半查找介紹

1.1 定義

折半查找也稱二分查找，是一種在有序數(shù)組中查找某一特定元素的搜索算法，每一次查找，搜索范圍均縮小一半，效率較高。如果數(shù)組是亂序狀態(tài)，則應(yīng)排序，再進(jìn)行查找。

1.2 基本原理

搜索過(guò)程從數(shù)組的中間元素開(kāi)始，如果中間元素正好是要查找的元素，則搜索過(guò)程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半 。

1.3 時(shí)間復(fù)雜度與空間復(fù)雜度

總共有n個(gè)元素，每次查找的區(qū)間大小就是n，n/2，n/4，…，n/ 2 k 2^k 2k，一直到1，其中k就是循環(huán)的次數(shù)。

由于n/ 2 k 2 ^ k 2k取整后>=1，即令n/ 2 k 2^k 2k=1，可得k=log2n,（是以2為底，n的對(duì)數(shù)），所以時(shí)間復(fù)雜度可以表示O()=O(logn)。

二分查找只需要額外存儲(chǔ)三個(gè)變量：最大值 ，最小值 和 中點(diǎn)，空間復(fù)雜度為常數(shù) O(1)。

1.4 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：比較次數(shù)少，查找速度快，平均性能好。

缺點(diǎn)：要求待查表為有序表，且插入刪除困難。

2. 代碼實(shí)現(xiàn)

2.1 代碼設(shè)計(jì)

1. 輸入需要查找的元素，我們輸入的是38；left是有序數(shù)組最左端0，是最小值，right是有序數(shù)組最右端10，是最大值，mid為數(shù)組1/2位置，即array[5]；
2. 38比array[5] = 19大，因此left等于原mid+1，即array[6] = 26，right不變；新mid為(left+right)/2 = （6+10）/2 = 8；
3. 38比array[8] = 36大，因此left等于上一次mid+1，即array[9] = 38，right不變；新mid為(left+right)/2 = （9+10）/2 = 9；
4. 38等于array[9]，mid與left重合， 查找成功，返回?cái)?shù)組下標(biāo)9.

2.2 代碼實(shí)現(xiàn)

#include <stdio.h>
#include <string.h>
int binarySearch(int array[],int len,int target){
    int left = 0;
    int right = len - 1;
    while(left <= right){
        int mid = (right + left) / 2;
        if(array[mid] == target){
            return mid;
        } else if(array[mid] < target){
            left = mid + 1;
        } else if(array[mid] > target){
            right = mid - 1;
        }
    }
    return -1;
}
int main(void)
{
    int array[]={2,3,4,5,15,19,26,27,36,38,45};
    int key = 0,ret;
    printf("請(qǐng)輸入需要查找的數(shù)字:");
    scanf("%d",&key);
    ret = binarySearch(array,sizeof(array)/sizeof(int),key);
    if(ret < 0)
        printf("查找失敗\n");
    else
        printf("該數(shù)字為數(shù)組第%d個(gè)元素\n",ret+1);
    return 0;
}

運(yùn)行結(jié)果：

請(qǐng)輸入需要查找的數(shù)字:38

該數(shù)字為數(shù)組第10個(gè)元素