LeetCode刷题笔记(三): 二分查找

二分查找算法的核心思想：二分查找也常被称为二分法或者折半查找 (binary search, bisect)，每次查找时通过将待查找的单调区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为O(n)的数组，二分查找的时间复杂度为O(logn)。

一、求开方

题目：x 的平方根
给定一个非负整数 x，求它的开方，向下取整。

解答：

int mySqrt(int x) {
    int l = 1, r = x, mid, x_div_mid;
    while (l <= r) {
        mid = l + (r - l) / 2;
        x_div_mid = x / mid;
        if (mid == x_div_mid) {
            return mid;
        }
        if (mid < x_div_mid) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return r;
}

解答二：

int mySqrt(int x) {
    long t = x;
    while (t * t > x) {
        t = (t + x / t) / 2;
    }
    return t;
}

提示：使用除法可以防止溢出，也可以使用牛顿迭代法: 其公式为 $t_{n+1}=t_{n}−\frac{f(t_{n})}{f′(t_{n})}$。给定$f(t)=t2−x=0$，这里的迭代公式为 $t_{n+1}=\frac{t_{n}+\frac{x}{t_{n}}}{2}$。

二、查找区间

题目：在排序数组中查找元素的第一个和最后一个位置
给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置。

解答：

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

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

vector<int> searchRange(vector<int> &nums, int target) {
    if (nums.empty()) {
        return vector<int>{-1, -1};
    }
    int lower = lowerBound(nums, target);
    int upper = upperBound(nums, target) - 1;
    if (lower == nums.size() || nums[lower] != target) {
        return vector<int>{-1, -1};
    }
    return vector<int>{lower, upper};
}

提示：注意当要查找第一个出现的位置时，l要尽可能的小，也就是必须大于才会等于mid+1，最大值则是等于。

三、查找峰值

题目：寻找峰值
给定一个数组，定义峰值为比所有两边都大的数字，求峰值的位置。一个数组里可能存在多个峰值，返回任意一个即可。时间复杂度要求为 O(log⁡n)。

解答：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int length = nums.size();
        if (nums.size() == 1) return 0;
        if (nums[0] > nums[1]) return 0;
        if (nums[length - 1] > nums[length - 2]) return length - 1;
        int low = 1, high = length - 2, middle = (low + high) >> 1;
        while (low <= high) {
            if (nums[middle] > nums[middle + 1] && nums[middle] > nums[middle - 1])
                return middle;
            else if (nums[middle] <= nums[middle - 1])
                high = middle - 1;
            else low = middle + 1;
            middle = (low + high) >> 1;
        }
        return -1;
    }
};

提示：注意边界值。

四、旋转数组查找数字

题目：搜索旋转排序数组 II
一个原本非递减序的数组被首尾相连后按某个位置断开（如 [1,2,2,3,4,5] → [2,3,4,5,1,2]，在第一位和第二位断开），我们称其为旋转数组。给定一个值，判断这个值是否存在于这个旋转数组中。

解答：

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1, middle = (low + high) >> 1;
        while (low <= high) {
            if (target > nums[middle]) {
                if (nums[middle] > nums[high] || nums[high] >= target) low = middle + 1;
                else --high;
            } else if (target < nums[middle]) {
                if (nums[middle] < nums[high] || nums[low] <= target) high = middle - 1;
                else ++low;
            } else return true;
            middle = (low + high) >> 1;
        }
        return false;
    }
};

提示：注意旋转数组的性质，旋转到后面的数的最大值一定小于等于旋转到前面的最小值。

五、练习

题目一：寻找旋转排序数组中的最小值 II
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个可能存在重复元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

解答：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int len = nums.size();
        int low = 0, high = len - 1, mid = (low + high) >> 1;
        while (low <= high) {
            if (nums[mid] > nums[high]) low = mid + 1;
            else if (nums[low] < nums[high]) high = mid - 1;
            else --high;
            mid = (low + high) >> 1;
        }
        return nums[low];
    }
};

提示：想想为什么high--。

题目二：有序数组中的单一元素
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。

解答：

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int len = nums.size() - 1;
        if (len == 0) return nums[len];
        if (nums[0] != nums[1]) return nums[0];
        if (nums[len] != nums[len - 1]) return nums[len];
        int low = 0, high = len, mid = (low + high) >> 1;
        while (low <= high) {
            if (mid % 2 == 0) {
                if (nums[mid] == nums[mid + 1])
                    low = mid + 1;
                else high = mid - 1;
            } else {
                if (nums[mid] == nums[mid - 1])
                    low = mid + 1;
                else high = mid - 1;
            }
            mid = (low + high) >> 1;
        }
        return nums[low];
    }
};