刷题-Leetcode-数组

知识点

vector

是容器，vector的底层是array

C++中二维数组在地址空间上是连续的，相邻两个差了四个字节

查找

1. 二分法

   二分查找的基础条件是有序数组。

   数组是有序数组，都可以想一想是否可以使用二分法.

排序

刷题-Leetcode-35. 搜索插入位置

题目链接

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/search-insert-position

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目分析

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        //1.暴力
        //时间o(n) 
        //空间o(1)
        // for(int i = 0; i < nums.size(); i++){
        //     if(nums[i] >= target){
        //         return i;
        //     }
        // }
        // //此时只有情况3没有考虑到 target要比数组所有值大
        // return nums.size();

        //2.二分 [left,right]
        int n = nums.size();
        int left = 0;
        int right = n - 1;
        while(left <= right){
            int middle = left + (right - left) / 2;
            if(target > nums[middle]){
                left = middle + 1;
            }else if(target < nums[middle]){
                right = middle - 1;
            }else{
                return middle;
            }
        }
        // return left + 1;//不可以
        return right + 1;
    }
};