【算法】代码随想录之数组（更新中）

文章目录

前言

一、二分查找法（LeetCode--704）

二、移除元素（LeetCode--27）

前言

跟随代码随想录，学习数组相关的算法题目，记录学习过程中的tips。

一、二分查找法（LeetCode--704）

【1】算法功能：在有序数组中，查找指定元素，时间复杂度为O(log N)。

【2】算法思想：定义首尾指针分别指向数组的首尾元素，若中间元素的值小于目标值则将首指针移动至中间元素右侧，若中间元素的值大于目标值则将尾指针移动至中间元素的左侧，若相等则返回下标。

【3】代码实现：在左闭右闭的区间内查找。

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

【4】易错点：①注意while循环的判定条件；②注意high的更新条件。

二、移除元素（LeetCode--27）

在之前的刷题中已经遇到过，且代码随想录的解法与当时我的初次解法相同，见【LeetCode算法】第27题：移除元素-CSDN博客。