服务器网站备案,做网站公司如何赚钱,网站设计心的,施工企业质量发展规划这个算法的前提是#xff0c;数组是升序排列的 算法描述#xff1a;
i和j是指针可以表示查找范围
m为中间值
当目标值targat比m大时#xff0c;设置查找范围在m右边#xff1a;i m-1
当目标值targat比m小时#xff0c;设置查找范围在m左边#xff1a;j m1
当targat的…
这个算法的前提是数组是升序排列的 算法描述
i和j是指针可以表示查找范围
m为中间值
当目标值targat比m大时设置查找范围在m右边i m-1
当目标值targat比m小时设置查找范围在m左边j m1
当targat的值等于m时返回m的下标
如果最终没找到就返回-1 算法实现
public int birthDay(int[] a,int target){int i0;int ja.length-1;while(ij){int m (ij)/2;if(a[m]target){// 目标值在右边i m-1;} else if (targeta[m]) {// 目标值在左边j m - 1;}else if (a[m] target){//找到return m;}}return -1;
}public static void main(String[] args) {int targat4;a1 a1 new a1();int a[] new int[]{2,4,6,8,9};int numa1.birthDay(a,targat);System.out.println(num);
} 问题一为什么循环条件是ij 而不是ij 因为i 和 j 指向的元素也会参与比较最后m可以和i和j重叠 问题二(ij)/2有没有问题
在 Java 中表达式 int a (i j) / 2 的结果是向下取整。整数除法会丢弃小数部分 。但是如果遇到非常大的数字呢 Integer.MAX_VALUE 是 2147483647即 int 类型能够表示的最大值。
当第一次计算时i j 结果是 0 2147483647 2147483647。
当第二次计算时i 1073741824 和 j 2147483647。
i j 结果是 1073741824 2147483647 3221225471。
3221225471这个数字超过了整型能够表示的最大值所以变成了负数
public static void main(String[] args) {int i 0;int jInteger.MAX_VALUE;int m(ij)/2;System.out.println(m);System.out.println(————————————————————————————————————————————);i m1; //结果在右边m (ij)/2;System.out.println(m);
} 所以我们可以用移位运算符解决 将二进制数的每一位向右移动一位丢弃最右边的位同时在最左边填充零。
使得结果变为正整数
2^7 ------ 2^6 就可以代替/2 例如
1001 9
移位后
0100 4
