使用循环与递归的二分查找 博客分类: 数据结构与算法 算法
程序员文章站
2024-02-11 17:46:16
...
二分查找
简述:
二分查找主要用于在有序数组中查找某个数据项,具有查找速度快的优点,其算法所花时间与数据项的个数的比可用大O表示为O(logN)来表示。数据项的个数越多,越能反应出其优点。
循环
Code:
Long[] array; //表示一个Long型的数组引用, 需要初始化 int nElements; //表示数组中数据项的个数, 需要初始化 int compareTimes = 0; //定义比较次数 public int find(long searchKey) { int lowerBound = 0; //表示下界 int upperBound = nElements - 1; //表示上界 int curIn; while(true) { compareTimes++;//循环一次,比较次数加1 curIn = (lowerBound + upperBound) / 2; if (array[curIn] == searchKey) { return curIn; //找到所要查找的数据,位于array[curIn] } else if (lowerBound > upperBound) { return nElements; //范围不存在, 返回数据项的个数表示找不到数据 } else { if (array[curIn] > searchKey) { //查找数据位于array[lowerBound] - array[curIn]之间 upperBound = curIn - 1; //此时上界减1, 因为之前已经判断过array[curIn]和searchKey的值是否相等 } else { //查找数据位于array[curIn] - array[upperBound]之间 lowerBound = curIn + 1; //此时下界加1 } } } }
查找次数计算:
通过求以2为底,范围N的对数可得到二分查找所需要的比较次数。
比如范围为10,那么4次比较完全可以查找到任何该范围内的数,实际上可以涵盖范围为16的查找。2的3次方 < 10 < 2的4次方
使用二分查找来插入数据项
虽然比较次数变小了,但是数据项的移动仍然与线性插入一样,O(N).
public void insertByBinarySearch(long value) { int lowerBound = 0; //表示下界 int upperBound = nElements - 1; //表示上界 int curIn; while (true) { curIn = (lowerBound + upperBound) /2; //如果value的值和array[curIn]相等, 则插入到curIn+1的位置,原curIn右边的数据项右移. if (array[curIn] == value) { for (int k = nElements - 1; k > curIn; k--) { array[k+1] = array[k]; } array[curIn+1] = value; nElements++; compareNums++; //比较次数 break; } else if (array[curIn] > value) { //value的值小于array[curIn]. if (array[curIn-1] < value) { //value的值位于array[curIn-1]和array[curIn]之间. for (int k = nElements; k > curIn; k--) {//curIn及其后续的所有数据项依次右移 array[k] = array[k-1]; } array[curIn] = value; //在curIn位置插入value nElements++;//数据项个数+1 break; } else { //继续2分查找 upperBound = curIn -1; } compareNums++; //比较次数 } else { //value的值大于array[curIn]. if (value < array[curIn+1]) { //value的值位于array[curIn]和array[curIn+1]之间. for (int k = nElements - 1; k > curIn; k--) { //curIn+1及其后续的所有数据项依次右移 array[k+1] = array[k]; } array[curIn+1] = value;//在curIn位置插入value nElements++;//数据项个数+1 break; } else { //继续2分查找 lowerBound = curIn + 1; } compareNums++; //比较次数 } } }
递归
通常,递归的速度要比循环慢一些,但是递归的代码要简洁很多。
//对外提供的public方法, 调用private recFind()方法 public int find(long searchKey) { return recFind(searchKey, 0, nElements - 1); } private int recFind(long searchKey, int lowerBound, int upperBound) { int curIn; curIn = (lowerBound + upperBound) / 2; if (a[curIn] == searchKey) return curIn; else if (lowerBound > upperBound) return nElements; else { if (a[curIn] < searchKey) return recFind(searchKey, curIn + 1, upperBound); else { return recFind(searchKey, lowerBound, curIn - 1); } } }
推荐阅读
-
使用循环与递归的二分查找 博客分类: 数据结构与算法 算法
-
追MM与java的32种模式 博客分类: java Java设计模式算法数据结构QQ
-
PHP基于二分法实现数组查找功能示例【循环与递归算法】
-
数据结构与算法 递归--二分查找
-
二分查找算法的递归与非递归实现(C++)
-
算法与数据结构(13)—— 二分查找(递归与非递归)
-
算法设计与分析(第一篇)(分治与递归)(二分查找)在n+logn-2次比较中找出a[n]的最大元素与次大元素
-
PHP基于二分法实现数组查找功能示例【循环与递归算法】_php技巧
-
PHP基于二分法实现数组查找功能示例【循环与递归算法】
-
Java有序数组数据结构与二分查找算法的分析