二分查找的实现

1.1 什么是数据结构？

定义

在计算机科学领域，数据结构是一种数据组织、管理和存储格式，通常被选择用来高效访问数据

可以说，程序 = 数据结构 + 算法，它们是每一位程序员的基本功，下来我们通过对一个非常著名的二分查找算法的讲解来认识一下算法

1.2 二分查找

二分查找算法也称折半查找，是一种非常高效的工作于有序数组的查找算法

注意：一定要是排好序的数组中找。

1) 基础版

需求：在有序数组 A 内，查找值 target

如果找到返回索引

如果找不到返回 -1

算法描述：

前提	给定一个内含 n 个元素的有序数组 A，满足 A{0}\leq A{1}\leq A{2}\leq \cdots \leq A{n-1}$，一个待查值 target
1	设置 i=0，j=n-1
2	如果 i > j，结束查找，没找到
3	设置 m = (i + j)/ 2，m 为中间索引
4	如果 target < A{m} 设置 j = m - 1，跳到第2步
5	如果 A{m} < target$ 设置 i = m + 1，跳到第2步
6	如果 A{m} = target，结束查找，找到了

java 实现:

public class BinarySearch {
    public static void main(String[] arg){
        
        int[] nums={2,5,8,9,12,15,18};
     
        int indexs=binarySearch(nums, 8);
        System.out.print(indexs);
    }
    
    public static int ?binarySearch(int[] a,int target){
        int i=0; int j=a.length-1;
        while(i<=j){
            int m=(i+j)>>>1;
            if (target<a[m]) { ? ? ? ? // 在左边
                j=m-1;
            }else if (a[m]<target) { ? // 在右边
                i=m+1;
            }else {
                return m;
            }
        }
        return -1;
    }
}

2) 改变版

另一种写法:

public static int binarySearch(int[] a, int target) {
 ? ?int i = 0, j = a.length;
 ? ?while (i < j) {
 ? ? ? ?int m = (i + j) >>> 1; ? ? ? ? ?//>>>相当于除一个 2
 ? ? ? ?if (target < a[m]) {            // 在左边
 ? ? ? ? ? ?j = m;
 ? ? ?  } else if (a[m] < target) {     // 在右边
 ? ? ? ? ? ?i = m + 1;
 ? ? ?  } else {
 ? ? ? ? ? ?return m;
 ? ? ?  }
 ?  }
 ? ?return -1;
}

i,j 对应着搜索区间 [0,a.length)（注意是左闭右开的区间），i<j 意味着搜索区间内还有未比较的元素，j 指向的一定不是查找目标

思考：为啥这次不加 i==j 的条件了？

回答：这回 j 指向的不是查找目标，如果还加 i==j 条件，就意味着 j 指向的还会再次比较，找不到时，会死循环

如果某次要缩小右边界，那么 $j=m$，因为此时的 $m$ 已经不是查找目标了

#####

理解：

二分本质就是讲遍历查找的O(n)减少到O(logn）

j 和 a.length是数据， 减号是运算符， 在底层是要做运算的。 去掉两个减号， 那显然是优化了很多关键，就在第二处改动和第三处改动，基础版的j是m-1，可以达成i > j 的循环退出条件

1.3 衡量算法好坏

时间复杂度

计算机中，时间复杂度是用来衡量：一个算法的执行，随数据规模增大，而增长的时间成本，不依赖于环境因素

空间复杂度

与时间复杂度类似，一般也使用大 O 表示法来衡量：一个算法执行随数据规模增大，而增长的额外空间成本

二分查找性能

下面分析二分查找算法的性能

时间复杂度

最坏情况：O(log n)

最好情况：如果待查找元素恰好在数组中央，只需要循环一次 O(1)

空间复杂度

需要常数个指针 i,j,m，因此额外占用的空间是 O(1)$

注意：

遍历数组，最坏情况需要对整个数组进行查找，而二分法最坏情况只是数组的一半。我们可以把排好序的数据存下来，之后直接使用，而线性查找需要每次都要每次全部遍历

习题

1) 二分查找(Leetcode 704题)

要点：减而治之，可以用递归或非递归实现

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1

例如

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
 ? ?
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1 ? ?

参考答案：可以用任意一种二分求解

public class BinarySearch {
    public static void main(String[] arg){
        
        int[] nums={2,5,8,9,12,15,18};
     
        int indexs=binarySearch(nums, 8);
        System.out.print(indexs);
    }
    
    public static int ?binarySearch(int[] a,int target){
        int i=0; int j=a.length-1;
        while(i<=j){
            int m=(i+j)>>>1;
            if (target<a[m]) { ? ? ? ? // 在左边
                j=m-1;
            }else if (a[m]<target) { ? // 在右边
                i=m+1;
            }else {
                return m;
            }
        }
        return -1;
    }
}

2) 搜索插入位置(Leetcode 35题)

要点：理解谁代表插入位置

给定一个排序数组和一个目标值

在数组中找到目标值，并返回其索引

如果目标值不存在于数组中，返回它将会被按顺序插入的位置

例如

输入: nums = [1,3,5,6], target = 5
输出: 2
?
输入: nums = [1,3,5,6], target = 2
输出: 1
?
输入: nums = [1,3,5,6], target = 7
输出: 4

参考答案1：用二分查找基础版代码改写，基础版中，找到返回 m，没找到 i 代表插入点，因此有

public int searchInsert(int[] a, int target) {
 ? ?int i = 0, j = a.length - 1;
 ? ?while (i <= j) {
 ? ? ? ?int m = (i + j) >>> 1;
 ? ? ? ?if (target < a[m]) {
 ? ? ? ? ? ?j = m - 1;
 ? ? ?  } else if (a[m] < target) {
 ? ? ? ? ? ?i = m + 1;
 ? ? ?  } else {
 ? ? ? ? ? ?return m;
 ? ? ?  }
 ?  }
 ? ?return i; // 原始 return -1
}

3) 搜索开始结束位置(Leetcode 34题)

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

例如

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
?
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
?
输入：nums = [], target = 0
输出：[-1,-1]

参考答案

public static int left(int[] a, int target) {
 ? ?int i = 0, j = a.length - 1;
 ? ?int candidate = -1;
 ? ?while (i <= j) {
 ? ? ? ?int m = (i + j) >>> 1;
 ? ? ? ?if (target < a[m]) {
 ? ? ? ? ? ?j = m - 1;
 ? ? ?  } else if (a[m] < target) {
 ? ? ? ? ? ?i = m + 1;
 ? ? ?  } else {
 ? ? ? ? ? ?candidate = m;
 ? ? ? ? ? ?j = m - 1;
 ? ? ?  }
 ?  }
 ? ?return candidate;
}
?
public static int right(int[] a, int target) {
 ? ?int i = 0, j = a.length - 1;
 ? ?int candidate = -1;
 ? ?while (i <= j) {
 ? ? ? ?int m = (i + j) >>> 1;
 ? ? ? ?if (target < a[m]) {
 ? ? ? ? ? ?j = m - 1;
 ? ? ?  } else if (a[m] < target) {
 ? ? ? ? ? ?i = m + 1;
 ? ? ?  } else {
 ? ? ? ? ? ?candidate = m;
 ? ? ? ? ? ?i = m + 1;
 ? ? ?  }
 ?  }
 ? ?return candidate;
}
?
public static int[] searchRange(int[] nums, int target) {
 ? ?int x = left(nums, target);
 ? ?if(x == -1) {
 ? ? ? ?return new int[] {-1, -1};
 ?  } else {
 ? ? ? ?return new int[] {x, right(nums, target)};
 ?  }
}