首页 > 代码库 > 二分搜索 一种比较完美的实现方法
二分搜索 一种比较完美的实现方法
二分搜索，也称二分查找、折半搜索，是一种在有序数组中查找特定元素的搜索算法。搜索从数组的中间元素开始，如果中间元素刚好是要查找的元素，则搜索结束，如果要查找的特定元素大于（小于）中间元素，则在数组大于（小于）中间元素的一半中查找。该算法的递归实现比较容易理解，思路更清晰，但效率方面仍有提高的空间。
代码如下：
//递归版本int binary_search( const int arr[], int low, int high, int key){ int mid = low+(high-low)/2; // Do not use (low+high)/2 which might encounter overflow issue if(low>high) return -1; else { if(arr[mid]==key) return mid; else if(arr[mid]>key) return binary_search(arr,low,mid-1,key); else return binary_search(arr,mid+1,high,key); }}
需要注意的是int mid = low+(high-low)/2;而不是(low+high)/2，避免了溢出的情况。
但是当有序数组存在等值时，该方法需要根据指定的规则选取第一个（最后一个）的等值，此时只需要从mid向前（后）寻找即可。
由于寻找第一个、最后一个等值的时候，每次移动的步长为1，移动效率较低，此时可以再次使用二分查找的方法，加快寻找速度。
代码如下：
#include <cstdio>//flag 1表示查找第一个等值 0查找最后一个等值 int binarySearch(int *data, int length,int val,int flag){ if(!data)return -1; int left,right,res; left = 0; right = length-1; res = -1; while(left<=right) { int mid = left + (right-left)/2; if(data[mid]==val) { res = mid; if(flag==0) { right=mid-1; } else if(flag==1) { left=mid+1; } else return mid;//返回索引值 } else if(data[mid]<val) left=mid+1; else right= mid-1; } return res;}int main(){ int data[10]={ 4,5,23,60,60,86,88,89,89,101 }; printf("%d\n",binarySearch(data,10,4,1)); printf("%d\n",binarySearch(data,10,60,1)); printf("%d\n",binarySearch(data,10,60,0)); printf("%d\n",binarySearch(data,10,55,0)); printf("%d\n",binarySearch(data,10,89,0)); printf("%d\n",binarySearch(data,10,89,1)); printf("%d\n",binarySearch(data,10,4,0)); printf("%d\n",binarySearch(data,10,100,0));}
二分搜索 一种比较完美的实现方法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。