首页 > 代码库 > 二分查找法
二分查找法
分别用循环和递归实现二分查找
#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");}
二分查找法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。