10.二分查找

1.概念

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
时间复杂度:log(n)

2.实现

下述的实现依赖一个前提:列表中没有重复的元素
递归与非递归

package Search;

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        if (arr == null || arr.length <= 0) {
            return -1;
        }

        return __binarySerch(arr, 0, arr.length - 1, target);
    }

    private static int _binarySearch(int[] arr, int l, int r, int target) {
        int mid = l + (r - l) / 2;
        // 递归终止条件
        if (l > r) {
            return -1;
        }
        // 递归终止条件1
        if (target == arr[mid]) {
            return mid;
        } else if (target > arr[mid]) {
            return _binarySearch(arr, mid + 1, r, target);
        } else {
            return _binarySearch(arr, l, mid - 1, target);
        }
    }

    // 非递归实现
    private static int __binarySerch(int arr[], int l, int r, int target) {
        // 加上等号，用特殊值判断即可
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
        System.out.println(binarySearch(arr, 6));
    }
}

3.分析使用的场景

• 查找依赖的是顺序表结果，即数组；
  二分查找依赖根据下标随机访问的能力；
• 适用于有序列表
  同时适用的场景是一次排序多次查找，如果是频繁地查找和删除。
  针对动态变化的数据集合，二分查找将不再适用，比较适合适用二叉树；
• 不太适合数据量太大的列表
  因为需要连续的内存空间
  但是相比较于二叉树和散列表，二分查找不需要额外的内存空间。

4.二分查找变种

针对的是存在重复元素的数组

image.png

4.1 查找第一个值等于给定值的元素

如果我们求解的是第一个值等于给定值的元素，当 a[mid]等于要查找的值时，我们就需要确认一下这个 a[mid]是不是第一个值等于给定值的元素。
我们重点看第 11 行代码。如果 mid 等于 0，那这个元素已经是数组的第一个元素，那它肯定是我们要找的；如果 mid 不等于 0，但 a[mid]的前一个元素 a[mid-1]不等于 value，那也说明 a[mid]就是我们要找的第一个值等于给定值的元素。

// 非递归实现,查找第一个值等于给定值的元素
    private static int __binarySerch(int arr[], int l, int r, int target) {
        // 加上等号，用特殊值判断即可
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] == target) {
                // 如果该值在左端(mid==0)或者前一个值不等于中间值，则符合要求
                if (mid == 0 || arr[mid - 1] != arr[mid]) {
                    return mid;
                }
                r = mid - 1;
            } else if (arr[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }

4.2 查找最后一个值等于给定值的元素

// 递归实现,查找最后一个值等于给定值的元素
    private static int __binarySerch2(int arr[], int l, int r, int target) {
        // 递归结束条件
        if (l > r) {
            return -1;
        }
        int mid = l + ((r - l)) / 2;
        if (arr[mid] == target) {
            if (mid == arr.length - 1 || arr[mid + 1] != arr[mid]) {
                return mid;
            } else {
                return __binarySerch2(arr, mid + 1, r, target);
            }
        } else if (arr[mid] < target) {
            return __binarySerch2(arr, mid + 1, r, target);
        } else {
            return __binarySerch2(arr, l, mid - 1, target);
        }
    }

4.3查找第一个大于等于给定值的元素

一开始被误导了，其实这题比之前的更简单，如果中点值大于等于给定值，那么判断是否是临界值，不是的话继续循环；如果中点值小于给定值也是继续循环

// 非递归实现,查找第一个大于给定值的元素
    private static int __binarySerch3(int arr[], int target) {
        int l = 0;
        int r = arr.length - 1;
        // 加上等号，用特殊值判断即可
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            // 情况一:中间值大于等于给定值
            if (arr[mid] >= target) {
                    //如果中间值是坐起第一个或者前一个值小于给定值，那么就是该值
                    if(mid==0||arr[mid-1]<target){
                        return mid;
                    }
                    r=mid-1;
            } else {
                // 情况二:中间值小于等于给定值
                l = mid + 1;
            }
        }
        return -1;
    }

4.4 查找最后一个小于等于给定值的元素

// 递归实现,查找最后一个小于等于给定值的元素
    private static int __binarySerch4(int arr[], int l, int r, int target) {
        // 递归结束条件
        if (l > r) {
            return -1;
        }
        int mid = l + (r - l) / 2;
        if (arr[mid] <= target) {
            if (mid == arr.length - 1 || arr[mid + 1] > target) {
                return mid;
            } else {
                return __binarySerch4(arr, mid + 1, r, target);
            }
        } else {
            return __binarySerch4(arr, l, mid - 1, target);
        }
    }

5.习题

69. x 的平方根

题目和上面的很类似，关键是要注意int溢出以及0的处理

class Solution {
    public int mySqrt(int x) {
        if(x==0){
            return 0;
        }
        return _mySqrt(x,1,x);
    }
    private int _mySqrt(int taregt,int l,int r){
        //这个其实用不到
        if(l>r){
            return -1;
        }
        int mid=l+((r-l)>>1);
        if(mid<=taregt/mid){
            if(mid==taregt||(mid+1)>taregt/(mid+1)){
                return mid;
            }
        return _mySqrt(taregt,mid+1,r);
        }else{
           return _mySqrt(taregt,l,mid-1);
        }
    }
}

33. 搜索旋转排序数组

首先取中点
如果arr[mid]==target 返回
然后判断[0,mid]是否是有序的？
再判断target是否在此区间
否则[mid,r]是有序的
再判断target是否在此区间
注意没有旋转的情况

class Solution {
    public int search(int[] nums, int target) {
        //异常情况
        if(nums==null||nums.length<=0){
            return -1;
        }
        //特殊情况
        if(nums.length==1){
            return target==nums[0]?0:-1;
        }
        //初始分界值
        int l=0;
        int r=nums.length-1;
        //终止条件
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[mid]==target){
                return mid;
            }
            //说明[0,mid]是有序的,等号主要考虑没有旋转的情况
            if(nums[mid]>=nums[0]){
                //判断target是否在此[0,mid]有序区间
                if(target>=nums[0]&&target<nums[mid]){
                    r=mid-1;
                }else{
                    l=mid+1;
                }
            }else{//说明[mid+1,r]是有序的
                //判断target是否在[mid,r]有序区间内
                if(target >nums[mid]&& target <=nums[r]){
                    l=mid+1;
                }else{
                    r=mid-1;
                }
            }
        }
        return -1;
    }
}