二分查找

参数： 有序数组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 = 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+1left = 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

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