二分查找

常见的查找算法有顺序查找、二分查找、插值查找,斐波那契查找,树表查找、分块查找、哈希查找等等。其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。

请记住凡是涉及到在**排好序的地方查找的都就可以考虑用二分来优化查找效率。**不一定全局都排好才行,只要某个部分是排好的,就可以针对该部分进行二分查找,这是很多题目优化查找的重要途径。

不去1/2,取1/3,3/4这样不是也可以吗?当然可以!为了更有通用性,插值查找使用的公式是:
mid=low+(key- a[low])/(a[high]-a[low])*(high-low)

1. 基本查找

时间复杂度为 O(n),很容易实现,但是效率低

int search(int[] a, int key) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == key) {
            return i;
        }
    }
    return -1;
}            return i;
        }
    }
    return -1;
}

2. 分治法

分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。

3. 二分查找

循环方式

细节就是+1和-1,不能忘记,nums[target]不是目标值,所有要排除

class Solution {
    public int search(int[] nums, int target) {
        int high = nums.length-1;
        int low = 0;
        while (high >= low) {
            int mid = (low + high) >> 1;
            if (target == nums[mid]) {
                return mid;
            }
            if (target > nums[mid]) {
                low = mid+1;
            }
            if (target < nums[mid]) {
                high = mid-1;
            }

        }
        return -1;
    }

}

递归方式

也是非常简单

class Solution {
    public int search(int[] nums, int target) {
        int high = nums.length - 1;
        int low = 0;
        return binarySearch2(nums, low, high, target);
    }

    public static int binarySearch2(int[] array, int low, int high, int target) {
        if (high < low) {
            return -1;
        }
        int mid = (high + low) >> 1;
        if (array[mid] == target)
            return mid;
        if (array[mid] < target)
            return binarySearch2(array, mid + 1, high, target);
        if (array[mid] > target)
            return binarySearch2(array, low, mid - 1, target);
        return -1;

    }
}

但是上面的两个方法虽然使用位运算,加快了速度,但是没有考虑到临界问题,比如low+high如果超过范围怎么办?

或许你想到了方法:利用数学性质,(a+b)/2 ==> b+ ((a-b)/2)

int mid = low+(high - low)>>1;  

但是结果是错的,因为移位的运算符>>优先级比加减要低,所以上面的代码等价结构是这样的:

(low+(high - low))>>1

解决方法是使用一个数学性质,加括号就行

int mid = low + ((high - low) >> 1);

循环方式完整代码

class Solution {
    public int search(int[] nums, int target) {
        if(nums==null||nums.length==0)return-1;
        int high = nums.length-1;
        int low = 0;
        while (high >= low) {
           int mid = low + ((high - low) >> 1);
            if (target == nums[mid]) {
                return mid;
            }
            if (target > nums[mid]) {
                low = mid+1;
            }
            if (target < nums[mid]) {
                high = mid-1;
            }

        }
        return -1;
    }

}

递归方式完整代码

class Solution {
    public int search(int[] nums, int target) {
        if(nums==null||nums.length==0)return-1;
        int high = nums.length - 1;
        int low = 0;
        return binarySearch2(nums, low, high, target);
    }

    public static int binarySearch2(int[] array, int low, int high, int target) {
        if (high < low) {
            return -1;
        }
         int mid = low + ((high - low) >> 1);
        if (array[mid] == target)
            return mid;
        if (array[mid] < target)
            return binarySearch2(array, mid + 1, high, target);
        if (array[mid] > target)
            return binarySearch2(array, low, mid - 1, target);
        return -1;

    }
}

4. 元素有重复的二分查找

试想一下,如果数组中存在重复元素 ,如何查找?

 public static int search1(int[] nums, int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0;

        if (nums[0] == target) {
            return 0;
        }

        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                //找到之后,往左边找
                

                while (mid != 0 && nums[mid] == target)
                    mid--;
                return mid + 1;
            }
        }
        return -1;
    }

这里需要注意,最后返回mid+1,是因为先mid--,指针已经到了需要的前一个,所以需要+1

例如假如序列为{1, 2, 2, 2, 2, 3, 3},当target=3,当内层的while退出时,nums[mid]=2,因此我们必须返回mid+1。