宁波网站建设信任荣盛网络,给小学生做家教的网站,世界网络公司排名前十,页面设计多少钱二分查找 二分查找思想应用于对有序的数组进行查找操作。 时间复杂度 二分查找也称为折半查找#xff0c;每次都能将查找区间减半#xff0c;这种折半特性算法时间复杂度为O(logn)。 mid计算 有两种计算中值mid的方式#xff1a; m(lh)/2ml(h-l)/2lh可能出现加法溢出#x…二分查找 二分查找思想应用于对有序的数组进行查找操作。 时间复杂度 二分查找也称为折半查找每次都能将查找区间减半这种折半特性算法时间复杂度为O(logn)。 mid计算 有两种计算中值mid的方式 m(lh)/2ml(h-l)/2 lh可能出现加法溢出也就是说加法的结果大于整形能够表示的范围。但是l和h都为正数因此h-l不会出现加法溢出的问题。所以最好使用第二种计算方法。 变种 二分查找可以有很多变种变种实现要注意边界值的判断。例如在一个有重复元素的有序数组中查找key的最左位置的实现如下 public int binarySearch(int []nums,int key){int l0;int hnums.length-1;while(lh){int ml(h-l)/2;if(nums[m]key){hm;}else{lm1;}}return l;
} 该实现和正常实现有以下不同 h的复制表达式为hm循环条件为lh最后返回的l而不是-1转载于:https://www.cnblogs.com/yjxyy/p/11106095.html
