代码随想录算法训练营第一天 | 二分查找

Leetcode704 二分查找

链接：https://leetcode.cn/problems/binary-search/
代码随想录: https://programmercarl.com/
时间复杂度: O(logN)
空间复杂度: O(1)

二分法的使用前提:

1. 没有重复元素
2. 数据结构是有序排列

区间选择

1. [left, right]: 此时left == right的条件是有意义的, 在更新左右索引时均取mid_index的下一位
2. [left, right): 此时循环条件为left < right. 若>= right则超过判断边界, 在更新右索引时取mid的值

其他注意事项

1. 避免数据溢出: mid_index = left + ((right - left) >> 1), 等同于(right + left) / 2, 但更安全高效
2. 除以2可以使用移位操作>> 1

int search(vector<int>& nums, int target) {if (nums.empty()) {return -1;}int left = 0, right = nums.size() - 1;while (left <= right) {int mid_index = left + ((right - left) >> 1);int mid_value = nums[mid_index];if (mid_value == target) {return mid_index;} else if (mid_value < target) {left = mid_index + 1;} else {right = mid_index - 1;}}return -1;
}

Leetcode27 移除元素

链接:https://leetcode.cn/problems/remove-element/
时间复杂度: O(N)
空间复杂度: O(1)

解题思路:

双指针法 即一个指针遍历数组, 一个指针指向需要更新的位置
该方法的问题是: 在最坏情况下, 如若开头第一个元素相等, 后续均不等, 则左指针指向的位置也需要更新n-1次. 该种情况下, 需要遍历该序列至多两次.

优化思路

int removeElement(vector<int>& nums, int val) {int val_index = 0;  // 数值索引for (int i = 0; i < nums.size(); i++) {if (nums[i] != val) {if (i != val_index) {  // 减少数据访问和赋值操作nums[val_index] = nums[i];}val_index++;}}return val_index;
}