二分查找算法java版实现(递归实现与非递归实现)
【摘要】 二分查找，如果一个有序集合，需要查找其他特定 的查询，我们可以使用二分查找，加快查询速度，具体的思路就是，每次取有序数组的中间元素与待查找元素进行比较，从而缩小一半的查询范围。
java版本非递归方式实现二分查找：
/** * * @param source * @param search * @return 返回匹配的下标 */ public stati...
二分查找，如果一个有序集合，需要查找其他特定 的查询，我们可以使用二分查找，加快查询速度，具体的思路就是，每次取有序数组的中间元素与待查找元素进行比较，从而缩小一半的查询范围。
java版本非递归方式实现二分查找：
-
/**
-
*
-
* @param source
-
* @param search
-
* @return 返回匹配的下标
-
*/
-
public static final int twoPointSearch(int[] source, int search) {
-
int min = 0;
-
int max = source.length - 1;
-
int mid = ( max - min ) >> 1 ;
-
-
while (mid >= 0 && mid <= max && max >= min) {
-
if(source[mid] == search ) {
-
return mid;
-
}
-
-
if(source[mid] > search ) { // 在souce前半部分查找
-
max = mid - 1;
-
} else { // 在souce后半部分查找
-
min = mid + 1;
-
}
-
-
mid = ((max-min) >> 1) + min ;
-
}
-
-
return -1;
-
}
-
/**
-
* 二分查找，递归版本
-
* @param source 有序数组
-
* @param search 待查询元素
-
* @param min 开始下标
-
* @param max 结束下标（初始值为有序数组长度减1）
-
* @return
-
*/
-
public static final int twoPointSearchByRecursion(int[] source, int search, int min, int max) {
-
int mid = ((max-min) >> 1) + min ;
-
-
if(mid >= 0 && mid <= max && max >= min ) {
-
if(source[mid] == search ) {
-
return mid; //返回下标
-
}
-
-
if(source[mid] > search ) { // 在souce前半部分查找
-
max = mid - 1;
-
} else { // 在souce后半部分查找
-
min = mid + 1;
-
}
-
-
return twoPointSearchByRecursion(source, search, min, max) ;
-
-
} //否则结束递归
-
-
return -1;
-
}
-
/**
-
* 二分查找
-
*/
-
public static final void testTwoPointSearch() {
-
-
int[] source = new int[] { 1,13,21,35,39,51,62,78,99 };
-
-
-
System.out.println(twoPointSearch(source, 22));
-
System.out.println(twoPointSearch(source, 21));
-
System.out.println(twoPointSearch(source, 1));
-
System.out.println(twoPointSearch(source, 99));
-
-
System.out.println(twoPointSearchByRecursion(source, 22, 0, source.length-1));
-
System.out.println(twoPointSearchByRecursion(source, 21, 0, source.length-1));
-
System.out.println(twoPointSearchByRecursion(source, 1, 0, source.length-1));
-
System.out.println(twoPointSearchByRecursion(source, 99, 0, source.length-1));
-
-
}
文章来源: blog.csdn.net，作者：中间件兴趣圈，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/prestigeding/article/details/72818506
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）