[每日学习]算法学习1——数组二分

回来啦！
开启新的一段时间的算法学习~
也可以说是复习+深入理解，程序员还是要好好打基本功的。

从数组开始。

数组 二分法

入门二分法

快速敲一遍代码，复习两种最常见的标准二分法。

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

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

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
1
2
3

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

解法一

区间定义：如果要查找的元素存在，那它一定在该区间内

// 左闭右开区间
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while(left < right) {
            int mid = (left + right) >>> 1;
            if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] > target) {
                right = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解法二

// 左闭右闭区间
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) >>> 1;
            if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

逼近类二分法

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 :

输入: 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
2
3
4
5
6
7
8

这道题相比上边第一题的变化，是本题找插入位置，即找到第一个大于等于target元素的位置。
当然，也可以理解为与第一题一样寻找target位置，那就是一个标准的二分法了，只需要在最后处理特殊边界情况即可。

解法一 首先来暴力解：

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 暴力解法
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }
}
1
2
3
4
5
6
7
8
9
10
11

解法二:

二分法上，与第一题的区别：

第一题区间定义：如果要查找的元素存在，那它一定在该区间内
本题区间定义：第一个大于等于target元素的位置，在该区间内

//  左闭右闭
class Solution {
    public int searchInsert(int[] nums, int target) {
        // 区间定义：第一个大于等于target元素的位置，在该区间[l, r]内
        // 特殊情况，target大于数组所有值，插入位置将在最后
        int l = 0;
        int r = nums.length - 1; // 虽然nums.length的位置也可能，但在左闭右闭区间中可能数组越界，单独考虑
        
        while(l <= r) {
            int mid = (l + r) >>> 1;
            if(nums[mid] < target) {
                l = mid + 1;
            } else if(nums[mid] > target) {
                r = mid - 1; // 注意
            } else {
                return mid;
            }
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

在l == r的时候，r = mid会无限循环，因此这里只能写r = mid - 1，但这不会影响二分法。
因为r = mid - 1排除了mid的位置，区间变为[l, mid - 1]，假设从某一步开始最终要找的就是mid位置， 定义为x，此时r为x - 1。后续l必然会一直逼近r，r不变，直到结束的时候，有 l = r + 1 = x, 我们最后返回l是正确的

解法三

//  左闭右开
class Solution {
    public int searchInsert(int[] nums, int target) {
        // 区间定义：第一个大于等于target元素的位置，在该区间[l,r)内
        // 特殊情况，target大于数组所有值，插入位置将在最后
        int l = 0;
        int r = nums.length;
        
        while(l < r) { // 当l == r区间已经非法了
            int mid = (l + r) >>> 1;
            if(nums[mid] < target) {
                l = mid + 1;
            } else if(nums[mid] > target) {
                r = mid; // 注意 
            } else {
                return mid;
            }
        }
        return l; // 最后l == r，所以返回哪个都可以
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

nums[mid] > target的时候，可能mid正好是我们要插入的位置
而这里可以写r = mid ，因为在l < r的情况下取中值mid绝不会等于r，不会死循环

简化一下写法：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0;
        int r = nums.length;
        while(l < r) {
            int mid = (l + r) >>> 1;
            if(nums[mid] < target) {
                l = mid + 1;
            } else { // 简化了，当nums[mid] == target时，r = mid
                r = mid;
            }                    
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

类似题目：
278. 第一个错误的版本

解法几乎完全一致，代码搬过来稍微改一下：

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1;
        int r = n;
        while(l < r) {
            int mid = (l + r) >>> 1;
            if(!isBadVersion(mid)) {
                l = mid + 1;
            } else {
                r = mid;
            }                    
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1] 输出：2 
解释：3 是峰值元素，你的函数应该返回其索引 2。 示例 2：

输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5  
解释：你的函数可以返回索引 1，其峰值元素为 2；  或者返回索引 5， 其峰值元素为 6。
1
2
3
4
5
6
7

这是一道中等题，看到O(log n)的复杂度要求就知道，本质也是二分法，而且分析一下，发现与上面两题解法完全一致

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while(l < r) {
            int mid = (l + r) >>> 1;
            if(nums[mid] < nums[mid + 1]) {
                l = mid + 1;
            } else {
                r = mid;
            }                    
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

拓展题目（待完成）：

34. 在排序数组中查找元素的第一个和最后一个位置
69.x 的平方根
367.有效的完全平方数

总结

二分法很重要，适用范围也很广，今天只是学了其中一部分。再次练习发现对它的理解又变深了一层，还是有收获的。