二分查找:递归实现
public class BinarySearch {
/**
* @param arr 代查找的数组，需要有序
* @param left 查找区间的左界限
* @param right 查找区间的右界限
* @param target 待查找的值
* @param <T> 泛型
* @return <p>在arr中[left...right]左闭右闭区间查找target, 找到了就返回该下角标，没找到则返回-1.<p/>
*/
public static <T extends Comparable<? super T>> int search(T[] arr, int left, int right, T target) {
if (left > right) return -1;//递归结束了都没找到，返回-1.
int mid = left + (right - left) / 2; // 二分，arr[mid]作为比较的基准值。
if (arr[mid].compareTo(target) == 0) {//如果相等，说明找到
return mid;
} else if (arr[mid].compareTo(target) < 0) {//如果中间的比target小，则在右半边找
return search(arr, mid + 1, right, target);
} else {////如果中间的比target大，则在左半边找
return search(arr, left, mid - 1, target);
}
}
public static <T extends Comparable<? super T>> int search(T[] arr, T target) {
return search(arr, 0, arr.length - 1, target);
}
public static void main(String[] args) {
Integer[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};//二分查找需要是有序的数组
int ret = search(arr, 11);
System.out.printf("下角标是：%d\n", ret);
}
}
二分查找：非递归实现
public class BinarySearch {
public static <T extends Comparable<? super T>> int search(T[] arr, T target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {//从[left ... right] 左闭右闭区间找,当left==right时，就是在判断arr[left]是否等于target
int mid = left + (right - left) / 2;
if (arr[mid].compareTo(target) < 0) {//如果中间的比target还小，那么到右半边去找
left = mid + 1;
} else if (arr[mid].compareTo(target) > 0) {//如果中间的比target大,那么到左半边去找
right = mid - 1;
} else {//如果 arr[mid] == target
return mid;
}
}
//如果没找到
return -1;
}
public static void main(String[] args) {
Integer[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};//二分查找需要是有序的数组
int ret = search(arr, 11);
System.out.printf("下角标是：%d\n", ret);
}
}
二分查找：求mid时除以2的bug问题
比如left = 1256648431, right = 1742321453 那么相加后就会上溢，得到结果 -1295997412, 除以2之后就是 -647998706,显然这个结果是不对的。
下面介绍三种方法，可以计算出正确的结果 1499484942
public class BinarySearch {
public static void main(String[] args) {
int a = 1256648431;
int b = 1742321453;
long c = (long) a + b;
System.out.printf("a + b 应该等于 %d ", c);//a + b 应该等于 2998969884 ,正确
System.out.printf("(a + b)/2 应该等于 %d\n\n", c / 2);//(a + b)/2 应该等于 1499484942 ,正确
System.out.println("整数int型用普通除法");
System.out.printf("a + b 等于 %d ", a + b);// -1295997412 ,溢出
System.out.printf("(a + b)/2 等于 %d\n\n", (a + b) / 2);// -647998706 ,溢出
System.out.println("整数int型用逻辑右移代替除法");
System.out.printf("a + b 等于 %d ", a + b);// -1295997412 ,溢出
System.out.printf("(a + b)>>>1 等于 %d\n\n", (a + b) >>> 1);// 1499484942 ,正确
System.out.println("整数int型用位运算技巧代替除法");
System.out.printf("a + b 等于 %d ", a + b);// -1295997412 ,溢出
System.out.printf("(a & b) + (a ^ b) >> 1 等于 %d\n\n", (a & b) + ((a ^ b) >> 1));// 1499484942 ,正确
}
}
最后一种情况，请查看该博客:用位运算求两个整型数的平均值（避免溢出）
给女朋友讲最后一种情况时的笔记：
目的：两个二进制数，对应位置进行相加,求出每项的项系数，也就是每位结果。
根据规律，分为两种情况。
1.对应位不同，其中一个为1，另一个为0
2.对应位相同，即同为1，或同为0
设a:1100110,b:1010101. 那么a + b = 2110211.(先不考虑进位)
处理情况1：去找规律，发现，情况为1时，相加总为1，相当于异或运算。对于情况2，异或运算总为0,不会被影响到。
处理情况2：再去找规律，发现，情况为2时，两数相加的结果要么是0,要么是2。结果总是‘&运算’结果的2倍。对于情况1，&运算结果总得到0,不会被影响到。 a:1100110
b:1010101
a^b:0110011 0 1 4 5 找到了这些项的系数
a&b:1000100 2 3 6 找到了这些项的系数
但上面这个与运算得出来的并不是真正的项系数，而是对应位置项系数的一般。所以 * 2后得
:2000200(先不考虑进位)
所以sum = (a & b) * 2 + (a ^ b)
sum / 2 = (a & b) + (a ^ b) / 2 (后续再把这个除法改成右移运算)
----------------------------------------------------------
或者换一种说法。
设a:1100110,b:1010101. 那么a + b = 2110211.(先不考虑进位)
对于a + b = 2110211.其中的2都是'&运算' 乘2得来,其中的1都是‘ ^运算 ’得来。