整数二分模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

No.367 有效的完全平方数

给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。

说明：不要使用任何内置的库函数，如  sqrt。

1
2
3
4
5
6
7
示例 1：
输入：16
输出：True

示例 2：
输入：14
输出：False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    // 二分法
    bool isPerfectSquare(int num) {
        return bsearch(0, num, num);
    }

    bool bsearch(long long l, long long r, long long num) {
        while (l < r) {
            long long mid = l + r >> 1;
            if (mid * mid > num) r = mid;
            else if (mid * mid == num) return true;
            else l = mid + 1;
        }
        // 跳出的结果为 l = r 或者 l > r
        if (l > r) return false;
        else return (l * l == num) ? true : false;
    }
};

剑指Offer No.53 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

1
2
3
4
5
6
7
示例 1:
输入: [0,1,3]
输出: 2

示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] != mid) r = mid;
            else l = mid + 1;
        }
        // 跳出时 l = r or l > r
        return r;
    }
};

No.162 寻找峰值

峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。

1
2
3
4
5
6
7
8
9
10
示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

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

说明:

你的解法应该是 O(logN) **时间复杂度的。

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
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        return bpeak(0, nums.size(), nums);
    }

    int bpeak(int l, int r, vector<int>& nums) {
        while (l < r) {
            int mid = (l + r) >> 1;
            if (mid == nums.size() - 1) {
                if (nums[mid] > nums[mid - 1]) return mid;
                return bpeak(l, mid - 1, nums);
            } else if (mid == 0) {
                if (nums[mid] > nums[mid + 1]) return mid;
                return bpeak(mid + 1, r, nums);
            } else {
                if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) return mid;
                else {
                    return bpeak(l, mid - 1, nums) >= 0 ? bpeak(l, mid - 1, nums) : bpeak(mid + 1, r, nums);
                }
            }
        }
        if (l == r && nums[l] > nums[l + 1]) return l;
        else return -1;
    }
};

No.33 搜索旋转排序数组

升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。

请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：
输入：nums = [1], target = 0
输出：-1
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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 1) return nums[0] == target ? 0 : -1;
        // 判断子数组是否严格递增
        // 如果左侧递增 且数字在范围内 则在左侧，否则在右侧
        // 如果右侧递增 且数字在范围内 则在右侧，否则在左侧
        // 因此要优先判断 递增数组在哪一侧
        int l = 0, r = nums.size();
        while(l < r) {
            int mid = l + r >> 1;
            if (nums[mid] == target) return mid;
            // 左侧递增
            else if (nums[mid] >= nums[l]) {
                // 是否在范围
                if (nums[l]<= target && nums[mid] >= target) r = mid;
                else l = mid + 1;
            }
            else {
                if (nums[mid]<= target && nums[r - 1] >= target) l = mid + 1;
                else r = mid;
            }
        }
        if (l == r && l < nums.size() && nums[l] == target) return l;
        return -1;
    }
};