C++ 数据结构与算法（一）（复杂度、数组 二分查找）

时间复杂度是一个函数，它定性描述该算法的运行时间。

假设算法的问题规模为n，算法的渐近时间复杂度，简称时间复杂度，记为 O ( f ( n ) ) O(f(n)) O(f(n))。

大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。
但是业内的一个默认规定，O代表的就是一般情况，而不是严格的上界。
深入探讨一个算法的实现以及性能的时候，就要时刻想着数据用例的不一样，时间复杂度也是不同的。

O(1)常数阶 < O ( log ⁡ n ) O(log n) O(logn)对数阶 < O ( n ) O(n) O(n)线性阶 < O ( n log ⁡ n ) O(nlog n) O(nlogn) < O ( n 2 ) O(n^2) O(n2)平方阶 < O ( n 3 ) O(n^3) O(n3)立方阶 < O ( 2 n ) O(2^n) O(2n)指数阶 < O ( n ! ) O(n!) O(n!) < O ( n n ) O(n^n) O(nn)log n忽略底数的描述

空间复杂度预估程序运行时占用内存的大小，而不是可执行文件的大小。

数组是存放在连续内存空间上的相同类型数据的集合。

在升序数组 nums 中寻找目标值 target，对于特定下标 i，比较nums[ i ] 和 target 的大小：

如果 n u m s [ i ] = t a r g e t nums[i] = target nums[i]=target，则下标 i 即为要寻找的下标;如果 n u m s [ i ] > t a r g e t nums[i] > target nums[i]>target，则 target只可能在下标i的左侧;如果 n u m s [ i ] < t a r g e t nums[i] < target nums[i]target只可能在下标i的右侧。

基于上述事实，可以在有序数组中使用二分查找寻找目标值，每次查找都会将查找范围缩小一半。

时间复杂度： O ( log ⁡ n ) O(log n) O(logn)，其中 n 是数组的长度空间复杂度： O ( 1 ) O(1) O(1)

每次循环中 left 和 right 共同约束了本次查找的范围， 要让本次循环与上一次循环查找的范围既不重复(重复了会引起死循环)， 也不遗漏， 并且要让 left 和 right 共同约束的查找的范围变得无意义时不再进行查找（即跳出 while）(否则会导致访问越界)， 这其实就是所谓的循环不变量。因此要清楚对查找区间的定义，在循环中根据查找区间的定义来做边界处理。

定义查找区间为 [left, right] 或 [left, right)，LeetCode示例：

class Solution {
public:
    int search(vector& nums, int target) {
       	// 1、定义查找区间为 [left, right]
        int left = 0;
        int right = nums.size() - 1; 	// [left, right]
        while (left <= right){
            int middle = left + (right - left) / 2; //防溢出
            if (nums[middle] > target){
                right = middle - 1;		// [left, right]
            }
            else if (nums[middle] < target){
                left = middle + 1;		// [left, right]
            }
            else{
                return middle;
            }
        }
        return -1;

        // 2、定义查找区间为 [left, right)
        int left = 0;
        int right = nums.size();			// [left, right)
        while (left < right){
            int middle = left + (right - left) / 2;
            if (nums[middle] > target){
                right = middle;				// [left, right)
            }
            else if (nums[middle] < target){
                left = middle + 1;			// [left, right)
            }
            else{
                return middle;
            }
        }
        return -1; // 查找失败
    }
};

class Solution {
public:
    // 无重复元素
    int searchInsert(vector& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right){
            int middle = left + (right - left) / 2;
            if (nums[middle] > target){
                right = middle - 1;
            }
            else if (nums[middle] < target){
                left = middle + 1;
            }
            else{ // nums[middle] == target
                return middle;    // 无重复元素
            }
        }
        return left; // = right + 1
    }
};

循环判断中，等于target的情况不跳出循环，继续移动搜索指针，最终将会导致 left = right + 1 的情况而跳出循环。

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right){
            int middle = left + (right - left) / 2;
            if (nums[middle] >= target){	// 大于或等于 即 左移right
                right = middle - 1;			// 最后一个小于 num 的位置索引
            }
            else{ // nums[middle] < target	// 小于	即 右移left
                left = middle + 1;			// 第一个大于或等于 num 的位置索引
            }
        }
        // 有重复元素
        // 寻找第一个大于或等于 num 的位置索引，返回left
        return left; // = right + 1
        // 寻找最后一个小于 num 的位置索引，返回right
        // return right;  // = left + 1
    }
};

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right){
            int middle = left + (right - left) / 2;
            if (nums[middle] > target){		// 大于 即 左移 right
                right = middle - 1;			// 最后一个小于或等于 num 的位置索引
            }
            else{ // nums[middle] <= target	// 小于或等于 即 右移left
                left = middle + 1;			// 第一个大于 num 的位置索引
            }
        }
        // 有重复元素
        // 寻找第一个大于 num 的位置索引，返回left
        return left; // = right + 1
        // 寻找最后一个小于或等于 num 的位置索引，返回right
        // return right;  // = left + 1
    }
};

1、遍历

class Solution {
public:
    vector searchRange(vector& nums, int target) {    
    // 1、遍历
        int n = nums.size();
        int left = -1;	//左边界
        int right = -1; //右边界
        for ( int i = 0; i < n; ++i){  // 从左往右遍历
            if (nums[i] == target){
               if (left == -1){
                   left = i;
                   right = i;
               }
               else{
                   right = i;
               }
           }    
        }
        return vector{left,right};
    }
};

2、 二分法

class Solution {
public:
    //   寻找第一个大于或等于 num 的位置索引, 找不到则返回数组长度 （相当于 35. 搜索插入位置）
    int search (vector& nums, int num) {    
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target){		// 大于或等于 即 左移right
                right = mid - 1;			// 最后一个小于 num 的位置索引
            }
            else{ // nums[mid] < target	// 小于	即 右移left
                left = mid + 1;			// 第一个大于或等于 num 的位置索引
            }
        }
        return left;    // 寻找第一个大于或等于 num 的位置索引，返回left
                        // 寻找最后一个小于 num 的位置索引，返回right
    }

    // 四种情况：
    //  1、target 小于 nums 中最小 : left = right = 0
    //  2、target 大于 nums 中最大 : left = right = nums.size()
    //  3、target 在 nums 大小范围内，但不在其中：left = right = search(nums, target + 1)
    //  4、target 在 nums 数组中：left < right
    vector searchRange(vector& nums, int target) {
        int left = search(nums, target);        //   寻找第一个大于或等于 target 的位置索引
        int right = search(nums, target + 1);   //   寻找第一个大于或等于 target+1 的位置索引
        if (left < right){
            return vector {left, right-1};
        }
        return vector {-1, -1};
    }
};

找到满足 k 2 ≤ x k^2 ≤ x k2≤x 的最大 k k k 值，即寻找最后一个 k 2 k^2 k2小于或等于 x x x 的位置索引。

class Solution {
public:
    // 二分查找
    int mySqrt(int x) {
        int left = 0;
        int right = x;
        int ans = 0;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if ((long long)mid * mid > x){
                right = mid - 1; // 寻找最后一个小于或等于 num 的位置索引
            }
            else{ // (long long)mid * mid <= x
                left = mid + 1;
            }
        }
        return right;
    }
};

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 0;
        int rigth = num;
        while (left <= rigth){
            int mid = left + (rigth - left) / 2;
            long square = (long) mid * mid;		
            if (square > num){      		// 二分查找条件
                rigth = mid - 1;
            }
            else if (square < num){
                left = mid + 1;
            }
            else{
                return true;
            }
        }
        return false;
    }
};