参数： 有序数组arr(这里按升序来讲)，待搜索的值target
根据以上步骤可以写出递归、和非递归两种二分查找的方法
代码实现
public static void main(String[] args) {
int arr[] = {1, 8, 10, 11,23,1000,1234};
//int resIndex = binarySearch(arr, 0, arr.length - 1, 11);
int resIndex = binarySearchNoRecur(arr,11);
System.out.println(resIndex);
}
/** 非递归二分查找
* @param arr 待查找的数组(升序
* @param target 需要查找的值
* @return 返回对应下标，-1表示没有找到
*/
public static int binarySearchNoRecur(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left target) {
right = mid - 1;//向mid的左边
} else {
left = mid + 1;//向mid 的右边
}
}
return -1;
}
/** 递归版二分查找
* @param arr 待查找的数组(升序
* @param target 需要查找的值
* @return 返回对应下标，-1表示没有找到
*/
public static int binarySearch(int[] arr, int left, int right, int target) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (target > midVal) { //向右递归
return binarySearch(arr, mid + 1, right, target);
} else if (target < midVal) { //向左递归
return binarySearch(arr, left, mid - 1, target);
} else {//找到
return mid;
}
}
整数溢出问题
出现原因：java 中的 int 总共就 32 位，正数上限的情况首位也只能是 0，其他位都可以是 1（就是 2^31-1 的情况）。但是如果正数过大了，例如 2^31，计算机不得不把首位变成 1，把它按照正常的方式输出了(把1作为符号位)，于是就成了负的值。
获取中间索引时 (left + right) / 2，如果left和right都特别大，那么就有可能超出整数锁能存储的最大值，从而出现整数溢出问题
如下情况，第二次的mid出现了整数溢出问题
int left = 0;
int right = Integer.MAX_VALUE - 1;
int mid = (left+right)/2;
System.out.println(mid);
//如果中间值小于目标值，需要更改左边界为mid+1
left = mid + 1;
mid = (left+right)/2;
System.out.println(mid);
1073741823
-536870913
如何避免？
方法一
把求中间值公式改为 left - left/2 + right/2 =》 left + (right - left)/2
由于两个大值相减(right – left)得到的值较小，就避免了溢出问题
方法二
无符号的右移运算代替除法
(left+right)/2 =》 (left+right)>>>1
本来溢出的二进制数符号位为负数，由于进行了移位，就不把最高位当成符号位，就解决了溢出问题
Original: https://www.cnblogs.com/weloe/p/16723894.html
Author: 秋玻
Title: 二分查找步骤及问题总结
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/585110/
转载文章受原作者版权保护。转载请注明原作者出处！