首页 > 代码库 > 二分查找算法
二分查找算法
折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
1 #include <iostream> 2 using namespace std; 3 4 int binarysearch(int key, int low, int high, const int array[]) 5 { 6 while (low <= high) 7 { 8 int mid = low+(high-low)/2;// should in while 9 if (key > array[mid])10 low = mid + 1;11 else if (key < array[mid])12 high = mid - 1;13 else14 return mid;15 }16 return -1; // didn‘t find17 }18 19 /* 递归版本20 int binarysearch(int key, int low, int high,const int arr[])21 {22 int mid = low + (high - low) / 2; // Do not use (low+high)/2 which might encounter overflow issue23 if (low>high)24 return -1;25 else26 {27 if (arr[mid] == key)28 return mid;29 else if (arr[mid]>key)30 return binarysearch(key, low, mid - 1, arr);31 else32 return binarysearch(key, mid + 1, high, arr);33 }34 }35 */36 37 void result(int a)38 {39 if (a == -1)40 cout << "binarysearch failed, not included" << endl;41 else42 cout << "binarysearch result is array number " << a << endl;43 }44 int main()45 {46 int array[10] = { 1, 3, 5, 8, 11, 19, 33, 45, 65, 99 };47 int a = binarysearch(5, 0, 9, array);48 int b = binarysearch(4, 0, 9, array);49 result(a);50 result(b);51 //system("pause");52 return 0;53 }
注意在非递归版本里面 int mid = low + (high - low) / 2; 应该在循环内部。
二分查找算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。