做网站傻瓜软件,东营做网站优化,网站打不开的原因,电商网站搭建二分查找一、思路二、实现代码#xff08;普通版#xff09;三、整数溢出问题四、改进代码一、思路 1.前提: 有已排序数组A (假设已经做好) 2.定义左边界L、 右边界R,确定搜索范围#xff0c;循环执行二分查找(3、4两步) 3.获取中间索引 M Floor((LR) 1/2) 4.中间素索引的值…
二分查找一、思路二、实现代码普通版三、整数溢出问题四、改进代码一、思路 1.前提: 有已排序数组A (假设已经做好) 2.定义左边界L、 右边界R,确定搜索范围循环执行二分查找(3、4两步) 3.获取中间索引 M Floor((LR) 1/2) 4.中间素索引的值 A[M] 与待搜索的值T进行比较 ①A[M]T 表示找到返回中间索引 ②A[M]T, 中间值右侧的其它元素都大于T,无需比较中间索引左边去找M- 1设置为右边界重新查找 ③A[M]T, 中间值左侧的其它元素都小于T,无需比较中间索引右边去找M 1设置为左边界重新查找 5.当LR时 表示没有找到应结束循环 二、实现代码普通版 public class BinarySearch {public static void main(String[] args){int[] array {1,5,8,11,19,22,31,35,40,45,48,49,50};int target48;int idxbinarySearch(array,target);System.out.println(idx);}//二分查找找到返回目标值下标没找到返回-1;public static int binarySearch(int[] a,int target){int L0;int Ra.length-1;int M;while (LR){M(LR)/2;if(a[M]target)return M;else if(a[M]target)RM-1;else if(a[M]target)LM1;}return -1;}
}三、整数溢出问题
问题上述代码中如果 int L0; int RInteger.MAX_VALUE-1; 那么在第二次二分时将出现M超过int的取值范围导致上溢出。
解决方法 ①通过等价运算解决 m(rl)/2l/2r/2l(-l/2r/2)l(r-l)/2; ②通过移位计算除法无符号右移因为下标非负 m(rl)/2lr)1 四、改进代码
public class BinarySearch {public static void main(String[] args){int[] array {1,5,8,11,19,22,31,35,40,45,48,49,50};int target48;int idxbinarySearch(array,target);System.out.println(idx);}//二分查找找到返回目标值下标没找到返回-1;public static int binarySearch(int[] a,int target){int L0;int Ra.length-1;int M;while (LR){//改进代码无符号右移计算除法M(LR)1;if(a[M]target)return M;else if(a[M]target)RM-1;else if(a[M]target)LM1;}return -1;}
}
