首页 > 代码库 > 二分查找法

二分查找法

分别用循环和递归实现二分查找

#include <iostream>using namespace std;int binarysearchiteratively(int *data, int start, int end, int k){    int l = start - 1;    int r = end + 1;    while (l + 1 != r){        int middle = (l + r) / 2;        if (data[middle] == k) return middle;        else{            if (data[middle] < k) l = middle;            else{                r = middle;            }        }    }    return -1;}int binarysearchrecursively(int *data, int start, int end, int k){    if (start>end) return -1;    int middle = (start + end) / 2;    if (data[middle] == k){        return middle;    }    else{        if (data[middle] < k){            return binarysearchrecursively(data,middle+1,end,k);        }        else{            return  binarysearchrecursively(data, start, middle - 1, k);        }    }}void test1(){    int a[] = { 1, 2, 3 };    int result1 = binarysearchiteratively(a, 0, 2, 1);    int result2 = binarysearchrecursively(a, 0, 2, 1);    if (result1 == 0 && result2 == 0){        printf("%s\n", "test1 succeeded");    }    else{        printf("%s\n", "test1 failed");    }}void test2(){    int a[] = { 1, 2, 3 };    int result1 = binarysearchiteratively(a, 0, 2, 4);    int result2 = binarysearchrecursively(a, 0, 2, 4);    if (result1 == -1 && result2 == -1){        printf("%s\n", "test2 succeeded");    }    else{        printf("%s\n", "test2 failed");    }}void test3(){    int a[] = { 1 };    int result1 = binarysearchiteratively(a, 0, 0, 1);    int result2 = binarysearchrecursively(a, 0, 0, 1);    if (result1 == 0 && result2 == 0){        printf("%s\n", "test3 succeeded");    }    else{        printf("%s\n", "test3 failed");    }}void test4(){    int a[] = { 1 };    int result1 = binarysearchiteratively(a, 0, 0, 2);    int result2 = binarysearchrecursively(a, 0, 0, 2);    if (result1 == -1 && result2 == -1){        printf("%s\n", "test4 succeeded");    }    else{        printf("%s\n", "test4 failed");    }}int main(){    test1();    test2();    test3();    test4();    system("pause");}

 

二分查找法