二分查找

参数： 有序数组arr(这里按升序来讲)，待搜索的值target

步骤

1. 定义左边界left和有边界right
2. 获取中间索引(整数) mid = (left+right)/2，注意：js只有小数，mid需要再取整
3. 中间索引的值arr[mid]与待搜索的值target进行比较
   • arr[mid] == target ，即为找到，返回中间索引mid
   • arr[mid] > target，说明要搜索的值在mid的左边(降序情况相反)，需要去mid的左边找，更改右边界right为mid-1，重新查找
   • arr[mid] < target，说明要搜索的值在mid的右边(降序情况相反)，需要去mid的右边找，更改左边界left为mid+1，重新查找
4. 查找(循环)的过程中如果left > right说明找不到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 = binarySearch(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 <= right) { //说明需要继续查找
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > 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

本来溢出的二进制数符号位为负数，由于进行了移位，就不把最高位当成符号位，就解决了溢出问题