二分查找

参数: 有序数组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 <= 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

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

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/weloe/p/16723894.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!