二分查找只是一个递归的问题,并不体现分治法的思想。
算法前件:带查找序列有序(从左到右,非减序或非升序)
基本思想:先将待查元素与中间元素比,若比中间元素大,则在序列的后一半继续查找;若比中间元素小,则在序列的前一半继续查找。
算法描述:
1.与待查序列第一个元素比,若等于,则返回该元素下标,结束比较
2.与待查序列最后一个元素比,若等于,则返回该元素下标,结束比较
3.与待查序列中间元素m比,
若等于,则返回该元素下标,结束比较
若比m大,则在将序列范围确定为元素m至最后一个元素,返回步骤一执行,继续上述过程。
若比m小, 则在将序列范围确定第一个元素至元素m中间,返回步骤一执行,继续上述过程。
递归结束:待查序列为空
核心代码:
int A[100]; int aim; //low,high分别表示待查序列的起点下标和终点下标 int find(int low,int high) { if(low>high) return -1; int mid=(low+high)/2; if(A[low]==aim) return low; if(A[high]==aim) return high; if(A[mid]==aim) return aim; if(A[mid]<aim) return find(mid+1,high-1); else return find(low+1,mid-1); }