二分查找算法(Java)

作者：一键难忘520 | 2024-08-14 02:16:33

踩

二分查找算法是在哪学到的java

今天在公司闲着蛋疼，网上瞎逛，偶然在InfoQ网站上看到一篇文章《计算机科学中最重要的32个算法》，原文地址：http://www.infoq.com/cn/news/2012/08/32-most-important-algorithms?utm_source=infoq&utm_medium=popular_links_homepage，里面就有二分查找算法，于是乎动手实现此算法，看自己是否掌握了，倒腾半天才写出来，汗颜哪。写下此文，一来回顾一下二分查找算法，而来警醒自己。

一、概念

二分查找算法也称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。

二、算法思想

搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

三、优缺点

二分查找算法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，二分查找算法适用于不经常变动而查找频繁的有序列表。

四、复杂度分析

(1) 时间复杂度

二分查找每次把搜索区域减少一半，时间复杂度为 $O\left( \log n \right)$ 。（n代表集合中元素的个数）

(2)空间复杂度

$O\left( 1 \right)$ 。

五、代码实现

(1) 迭代实现

publicstaticintbinarySearch(int[] arr,inttarget) { 
intbot =1; 
inttop = arr.length; 
while(bot <= top) { 
// 防止溢出 
intmid = (bot + top) >>>1; 
if(target > arr[mid]) { 
bot = mid +1; 
}elseif(target < arr[mid]) { 
top = mid -1; 
}else{ 
returnmid; 
} 
} 
return-1; 
} 

(2)递归实现

/** 
* 递归实现二分查找算法 
* 
* @param arr 
* @param fromIndex 
* @param toIndex 
* @param key 
* @return 
*/ 
publicstaticintbinarySearch(int[] arr,intfromIndex,inttoIndex,inttarget) { 
while(fromIndex <= toIndex) { 
// 防止溢出 
intmid = (fromIndex + toIndex) >>>1; 
if(arr[mid] < target) { 
returnbinarySearch(arr, mid +1, toIndex, target); 
}elseif(arr[mid] > target) { 
returnbinarySearch(arr, fromIndex, mid -1, target); 
}else{ 
returnmid; 
} 
} 
return-1; 
} 

总结：1、最开始在写代码的时候，没有考虑到溢出。

2、没想到用递归实现。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/977534