二分查找

基础不好还怎么继续塔塔开，这里再次好好分析一下两个模板

分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。
https://blog.csdn.net/xiao_jj_jj/article/details/106018702
当我们把二分的各种模板看作搜索区[left,right]的各种变体，就好理解很多了

分析

模板A

我喜欢叫做加减模板，在每次更新时都是对left/right进行加减处理
可以说是最常见的模板 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  int left = 0, right = nums.length - 1;
  while(left <= right){
    // Prevent (left + right) overflow 
    //利用mid = left + (right - left) / 2 ， 可以防止在计算(left+right)的时候超出范围
    int mid = left + (right - left) / 2;
    if(nums[mid] == target)
    { 
        return mid;
    }else if(nums[mid] < target) {
        left = mid + 1; 
    }else { 
        right = mid - 1; 
    }

  }

  // End Condition: left > right
  return -1;
}

和下面那位老兄相比，它的特征在于left <= right
以及left = mid + 1; ,left = mid + 1;
结束条件是left > right 也就是左侧超过右侧的时候

那么，我们一般用它做什么呢
查找，而且是数组中的单个索引确定的元素/条件
其关键属性可以总结为：
1.查找条件可以在不与元素的两侧进行比较的情况下确定
2.不需要后续处理，因为在每一步中都在检查是否找到，到达末尾还没有得到结果，那就是找不到了

经典的“猜数字”就是这种模板最简单的体现

高级模板A

一种以查找元素右邻居为核心的模板
或者说寻找左侧边界 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  int left = 0, right = nums.length;
  
  while(left < right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target)
    { 
        return mid; 
    }else if(nums[mid] < target){ 
            left = mid + 1; 
    }else { 
            right = mid; 
        }
  }

  // Post-processing:
  // End Condition: left == right
  if(left != nums.length && nums[left] == target) return left;
  return -1;
}

和经典模板最大的不同在于while(left < right) ,因为在二者重合的时候我们就会跳出来了
与之对应的是right = mid ,或者说在左移的时候，我们不令右界等于middle-1了
结束条件是left == right

1.查找条件需要访问元素的直接右邻居。
2.使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
3.保证查找空间在每一步中至少有 2 个元素。
4.需要进行后处理。 当你剩下 1 个元素时，循环/递归结束。 需要评估剩余元素是否符合条件。

可以看作一个不断“在右侧元素”上分析并排除的过程，也因此是right = mid;而非-1
当排除到只剩下left和right的时候，检查left是不是符合条件，如果是就可以了
如果不是，我们已经知道right = middle，已经判断过middle即right不行了。那此题肯定就无解了

典型例子是“寻找第一个错误版本”

高级模板C

再次加强版
需要访问当前索引及其在数组中的直接左右邻居索引来判断 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while (left + 1 < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

理解了模板B看它就还好了，它更进一步：判断的是左右两边的情况
所以，无论左右，更新都是等于middle了
在最后，我们会得到最终的3个元素，而进行后处理的时候剩下两个元素
那就是left和right了，检测它们是否符合条件即可

1.搜索条件需要访问元素的直接左右邻居。
2.使用元素的邻居来确定它是向右还是向左。
3.保证查找空间在每个步骤中至少有 3 个元素。
4.需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件

三模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// 二分查找 --- [left, right]
    // 数组已经是有序的了!
    public static int binarySerach1(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0, right = nums.length-1;
        while (left <= right) {
            // 防止溢出 等同于(left + right)/2
            int mid = left + (right-left)/2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                // target 在左区间，所以[left, middle - 1]
                right = mid-1;
            } else {
                // target 在右区间，所以[middle + 1, right]
                left = mid+1;
            }
        }

        return -1;
    }

    // 二分查找 --- [left, right)
    // 数组已经是有序的了!
    int binarySearch2(int[] nums, int target){
        if(nums == null || nums.length == 0)
            return -1;
        // 定义target在左闭右开的区间里，即：[left, right)
        int left = 0, right = nums.length;
        // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            }
            else if(nums[mid] < target) {
                //  target 在右区间，在[middle + 1, right)中
                left = mid + 1;
            }
            else {
                // target 在左区间，在[left, middle)中
                right = mid;
            }
        }

        // Post-processing:
        // End Condition: left == right
        if(left != nums.length && nums[left] == target) return left;
        return -1;
    }

    // 二分查找 --- (left, right)
    // 数组已经是有序的了!
    int binarySearch3(int[] nums, int target) {
        if (nums == null || nums.length == 0)
            return -1;

        int left = 0, right = nums.length - 1;
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                //  target 在右区间，在(middle, right)中
                left = mid;
            } else {
                // target 在左区间，在(left, middle)中
                right = mid;
            }
        }

        // Post-processing:
        // End Condition: left + 1 == right
        if(nums[left] == target) return left;
        if(nums[right] == target) return right;
        return -1;
    }

//-------------------------------------------------------------------------------------------
// 参考自：
// 作者：Jungle8884
// 链接：https://leetcode-cn.com/leetbook/read/binary-search/xe22ch/?discussion=hqOQPt
// 来源：力扣（LeetCode）
//-------------------------------------------------------------------------------------------

分析二分查找代码时，不要出现 else，全部展开成 else if 方便理解。 注意「搜索区间」和 while 的终止条件，如果存在漏掉的元素，记得在最后检查。 如需要搜索左右边界，只要在 nums[mid] == target 时做修改即可。搜索右侧时需要减一。

对于ABC三者，可以简单归结为：
A.在严格递增有序数组中寻找某个数
B.在有序数组中寻找某个数第一次出现的位置（或者在有序数组中寻找第一个大于等于某个数的位置）
C.已知有一个先严格递增后严格递减的数组，找数组最大值的位置

例题

猜数字(最经典的二分)

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

返回我选出的数字。

猜数字题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1 ; 
        int right = n ;
        int middle = 0;
        int result = 0 ; 

        while(left<=right){
            middle = left + (right - left)/2 ;
            if(guess(middle) == 0){
                result = middle ;
                break ; 
            }else{
                if(guess(middle) == -1){
                    //猜的更大了,左移
                    right = middle - 1 ;
                }else if(guess(middle) ==1){
                    //猜的小了，右移
                    left = middle + 1 ;
                }

            }
        }

        return result ;
    }
}

山脉函数题目

符合下列属性的数组 arr 称为 山脉数组 ：

arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
    arr[0] < arr[1] < ... arr[i-1] < arr[i]
    arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。

山脉函数题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        //本质就是返回最大值的索引下标
        int left = 0 ; 
        int right = arr.length - 1;
        int result = 0 ;
        int mid = 0 ;

        while(left<=right){
            mid = left + (right-left)/2 ;
            //开始判断两情况
            if(arr[mid]>arr[mid+1]){
                //midd大，说明还可以向左边缩进
                result = mid ; //更新result的数字
                right = mid -1;
            }else{
                //向右边找
                left = mid +1 ;
            }
        }

        return result ;
    }
}