通過(guò) while 循環(huán)的方式，簡(jiǎn)單實(shí)現(xiàn) C 語(yǔ)言的二分查找。

#include <stdio.h>

int binarySearch(int a[], int count, int key)
{
    int low = 0;
    int high = count-1;

    while (low <= high) {
        int mid = (low + high) / 2;
        
        printf("low is %d, high is %d, mid is %d, a[mid] is %d, key is %d \n", low, high, mid, a[mid], key);

        if (a[mid] == key) {
            printf("- match -\n");

            return mid;
        } else if (a[mid] > key) {
            printf("<- try\n");
            
            high = mid - 1;
        } else {
            printf("try ->\n");

            low = mid + 1;
        }
    }

    return -1;
}

int main() {
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8}; 
    
    printf("Input the key you want to search: \n");
    
    int key;
    scanf("%d", &key);

    int location = binarySearch(array, 8, key);

    if (location >= 0) {
        printf("Find successed. location is %d and find key is %d\n", location, array[location]);   
    } else {
        printf("Find failed.\n");
    }

    return 0;
}

運(yùn)行驗(yàn)證如下：

• key 在左側(cè)

?  C ./a.out
Input the key you want to search: 
1
low is 0, high is 7, mid is 3, a[mid] is 4, key is 1 
<- try
low is 0, high is 2, mid is 1, a[mid] is 2, key is 1 
<- try
low is 0, high is 0, mid is 0, a[mid] is 1, key is 1 
- match -
Find successed. location is 0 and find key is 1

• key 超出左側(cè)

?  C ./a.out
Input the key you want to search: 
0
low is 0, high is 7, mid is 3, a[mid] is 4, key is 0 
<- try
low is 0, high is 2, mid is 1, a[mid] is 2, key is 0 
<- try
low is 0, high is 0, mid is 0, a[mid] is 1, key is 0 
<- try
Find failed.

• key 在右側(cè)

?  C ./a.out
Input the key you want to search: 
8
low is 0, high is 7, mid is 3, a[mid] is 4, key is 8 
try ->
low is 4, high is 7, mid is 5, a[mid] is 6, key is 8 
try ->
low is 6, high is 7, mid is 6, a[mid] is 7, key is 8 
try ->
low is 7, high is 7, mid is 7, a[mid] is 8, key is 8 
- match -
Find successed. location is 7 and find key is 8

• key 超出右側(cè)

?  C ./a.out
Input the key you want to search: 
9
low is 0, high is 7, mid is 3, a[mid] is 4, key is 9 
try ->
low is 4, high is 7, mid is 5, a[mid] is 6, key is 9 
try ->
low is 6, high is 7, mid is 6, a[mid] is 7, key is 9 
try ->
low is 7, high is 7, mid is 7, a[mid] is 8, key is 9 
try ->
Find failed.

總結(jié)

主要需要考慮 mid 在 while 循環(huán)中的修改，對(duì)于邊界的情形，需要謹(jǐn)慎處理。

我在寫(xiě)的過(guò)程中，主要在以下三處出現(xiàn)過(guò)問(wèn)題：

• 這里需要注意，low 與 high 遇到的時(shí)候，就是數(shù)組結(jié)束的時(shí)候。

while (low <= high) {...}

• 當(dāng)找到的值比 key 大，這時(shí)候 key 在數(shù)組左側(cè)，所以把 high 調(diào)整為 mid 的左側(cè)一個(gè)，因?yàn)?mid 已經(jīng)校驗(yàn)過(guò)，所以需要減一。

high = mid - 1;

• 當(dāng)找到的值比 key 小，這時(shí)候 key 在數(shù)組右側(cè)，所以把 low 調(diào)整為 mid 的右側(cè)一個(gè)，因?yàn)?mid 已經(jīng)校驗(yàn)過(guò)，所以需要加一。

low = mid + 1;