这个算法的前提是,数组是升序排列的
算法描述:
i和j是指针可以表示查找范围
m为中间值
当目标值targat比m大时,设置查找范围在m右边:i =m-1
当目标值targat比m小时,设置查找范围在m左边:j =m+1
当targat的值等于m时,返回m的下标
如果最终没找到就返回-1;
算法实现:
public int birthDay(int[] a,int target){int i=0;int j=a.length-1;while(i<=j){int m= (i+j)/2;if(a[m]<target){// 目标值在右边i= m-1;} else if (target<a[m]) {// 目标值在左边j = m - 1;}else if (a[m] == target){//找到return m;}}return -1;
}public static void main(String[] args) {int targat=4;a1 a1= new a1();int a[]= new int[]{2,4,6,8,9};int num=a1.birthDay(a,targat);System.out.println(num);
}
问题一:为什么循环条件是i<=j ,而不是i<j?
因为i 和 j 指向的元素也会参与比较,最后m可以和i和j重叠
问题二:(i+j)/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 j=Integer.MAX_VALUE;int m=(i+j)/2;System.out.println(m);System.out.println("————————————————————————————————————————————");i= m+1; //结果在右边m= (i+j)/2;System.out.println(m);
}
所以我们可以用>>>移位运算符解决
>>> : 将二进制数的每一位向右移动一位,丢弃最右边的位,同时在最左边填充零。
使得结果变为正整数
2^7 ------> 2^6 就可以代替/2
例如:
1001 =9
移位后:
0100 = 4