二分查找并实现求数的平方根 |
您所在的位置：网站首页 › 二分法求平方根java › 二分查找并实现求数的平方根 |
|
1、二分查找 对一个有序的数据集合，查找的思想类似分治思想，每次通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。 /** * 注意在实现的时候： * 1、循环终止条件： low > 1) * 3、low和high的更新 * low = mid - 1; high = mid + 1，假如low == high，并且在mid位置不等于 value， * 那么容易造成死循环。 * * @param arr * @param val * @return */ public int bsearch(int[] arr, int val){ int low = 0; int high = arr.length - 1; // 查找指定元素 while(low > 1); if(arr[mid] == val){ return mid; } else if(arr[mid] > val){ high = mid - 1; }else if(arr[mid] < val){ low = mid + 1; } } return -1; }2、实现平方根，误差是小数点后6位 使用逐次逼近的方法，比如对6求根号，第一次取mid = 3，3*3 = 9 > 6，那么上限high = 3，第二次取1.5,1.5*1.5 = 2.25 < 6，那么更新下限 low = 1.5，接着mid = low + (high - low) / 2.0，然后接着更新上限或下限，直到误差在10^(-6)之内，就是得到的值，这里可以优化一下，任何数的平方根不会大于它的一半。当n大于4的时候，上述结论成立；若n小于等于4的时候，那么就改变策略，mid、high和low的取值改变一下即可，特殊处理一下。 /** * 使用二分查找实现平方根函数，要求精确到小数点后6位 */ public float sqrt_search(float n){ float mid = 0.0f; if(n < -1e-6){ // 小于0，抛异常 throw new IllegalArgumentException(); }else if(Math.abs(n) >= -1e-6 && Math.abs(n) 1e-6){ // 首先找到中间值 mid = low + (high - low) / 2; float tmp = mid * mid; // 比较并更新 high和low if((tmp - n) > 1e-6){ high = mid; }else if((tmp -n) < -1e-6){ low = mid; }else{ return mid; } } } return mid; }
|
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |