LeetCode.704.278.35(二分查找)

想了想，觉得还是从头系统地学习一下算法比较好，不然题刷了都记不住

704.二分查找

#include <vector>
using namespace std;
class Solution {
  public:
    int search(vector<int> &nums, int target) {
        /*int start = 0;
        int end = nums.size() - 1;
        while (end >= start) {
            if (nums[(end + start) / 2] < target) {
                start = (end + start) / 2 + 1;
            } else if (nums[(end + start) / 2] > target) {
                end = (end + start) / 2 - 1;
            } else
                return (end + start) / 2;
        }
        return -1;*/
        // 47/47 cases passed (36 ms)
        // Your runtime beats 30.04 % of cpp submissions
        // Your memory usage beats 16.35 % of cpp submissions (27 MB)
        //!他妈的要注意左边的+1和右边的-1
        int left = 0;
        int right = nums.size() - 1;                  // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) {                       // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2); // 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else {               // nums[middle] == target
                return middle;     // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
        // 47/47 cases passed (28 ms)
        // Your runtime beats 80.11 % of cpp submissions
        // Your memory usage beats 16.35 % of cpp submissions (27 MB)
        //把(end + start) / 2打包成middle更快
    }
};

278.第一个错误的版本

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
  public:
    int firstBadVersion(int n) {
        if (isBadVersion(1))
            return 1;
        int left = 1;
        int right = n;
        while (right > left + 1) {
            int middle = left + (right - left) / 2;
            if (isBadVersion(middle)) {
                right = middle;
            } else {
                left = middle;
            }
        }
        return right;
        // 22/22 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 39.66 % of cpp submissions (5.9 MB)
        //!注意第一个是不是坏版本
    }
};

35.搜索插入位置

以前做的又优化了一遍，记住了二分查找的解题思路了以后快很多(指写代码快很多)

#include <iostream>
#include <vector>
using namespace std;
class Solution {
  public:
    int searchInsert(vector<int> &nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (right >= left) {
            int middle = left + (right - left) / 2;
            if (nums[middle] > target)
                right = middle - 1;
            else if (nums[middle] < target)
                left = middle + 1;
            else
                return middle;
        }
        return left;
        // 64/64 cases passed (4 ms)
        // Your runtime beats 78.56 % of cpp submissions
        // Your memory usage beats 72.89 % of cpp submissions (9.4 MB)
        //老版本
        /*if (nums.at(0) > target) {
            nums.push_back(nums.at(nums.size() - 1));
            for (int i = nums.size() - 1; i > 0; i--) {
                nums.at(i) = nums.at(i - 1);
            }
            nums.at(0) = target;
            return 0;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums.at(i) == target) {
                return i;
            }
            if (nums.at(i) > target && nums.at(i - 1) < target) {
                nums.push_back(nums.at(nums.size() - 1));
                for (int j = nums.size() - 1; j >= i + 1; j--) {
                    nums.at(j) = nums.at(j - 1);
                }
                nums.at(i) = target;
                return i;
            }
        }
        if (nums.at(nums.size() - 1) < target) {
            nums.push_back(target);
            return nums.size() - 1;
        }
        return -1;*/
        // 62/62 cases passed (4 ms)
        // Your runtime beats 88.27 % of cpp submissions
        // Your memory usage beats 74.81 % of cpp submissions (9.3 MB)
        // FinishedTODO:代码有些复杂，有空的时候优化一下代码
    }
};