数组

June. 2024

01

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

注意:

• 如果一个问题,待查找的数是整数,且知道范围,大概就可以使用二分查找算法.
• 本题强调时间复杂度.

class Solution {
public:
    /**
        二分查找
        算法思路: 
            1.循环结束条件: 左值 > 右值
            2.每次循环要做的事: 判断左值和右值的中间位置的元素与目标值的关系
     */
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n-1, insert = n;
        while(left <= right){
            //在处理大整数时，直接计算 (left + right) / 2 可能会导致溢出，而通过 ((right - left) >> 1) + left 的方法则避免了这种情况
            int mid = ((right-left) >> 1) + left;
            if(target <= nums[mid]){
                insert = mid;
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return insert;
    }
};

Jul. 2024

01

TODO await 树

将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵平衡二叉搜索树。

02