代码随想录算法训练营第一天| 704. 二分查找，27. 移除元素

题目与题解

参考资���：数组理论基础

（）

704. 二分查找

题目链接：704. 二分查找

代码随想录题解：704. 二分查找

（）

视频讲解：

手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili

解题思路：

        二分法属于算法题中的基础，原理很简单，在一个已经排序且无重复元素的序列中查找一个给定值，只需要设置高低两个指针，每次用两个指针中间的值和目标值对比，如果目标值比中间值大，则目标值在中间指针和高指针之间；如果目标值比中间值小，则目标值在低指针和中间指针之间；如果找到目标，则返回中间指针所在。          初次解题通过的代码如下：         

class Solution {public int search(int[] nums, int target) {int len = nums.length;int low = 0, high = len - 1;while (low > 1代替

为提高算法效率，可以在一开始加上简单的前提条件避免极端情况

// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算        if (target  nums[nums.length - 1]) {            return -1;        }

遇到的困难

        第一次写的时候，没有考虑区间的问题，用了low

        还有就是很久不从头写代码，在Java中一般都习惯用List方法，突然要用数组类型有点不记得用法，后面题目做多了应该就习惯了。

27. 移除元素

题目链接：27. 移除元素

代码随想录题解：27. 移除元素

视频讲解：

数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili

解题思路

        数组相关的题，想要提高效率，要么是空间换时间，要么是时间换空间。

        首先，最容易想到的就是暴力方法，额外申请一个大小为n的新数组，遍历原数组，将符合要求的数塞入新数组，那么算法空间复杂度为n，时间复杂度为n。

        但是题目明确要求，只能原地修改数组，那么就只能用当前数组修改元素，最简单的暴力方法是使用两层for循环，当遍历到的元素等于目标值，则把该元素后面的所有元素往前挪一格，这样时间复杂度就是n2。

        如果想将时间复杂度降到n，则要考虑如何在每次循环判断时，只修改少量元素。由于元素的顺序可以修改，那么，可以设置前后两个指针，将当前等于val的元素与后指针指向的元素交换，并将后指针向前挪一格，直到循环到前后指针相遇。

初次解题结果如下：

class Solution {    public int removeElement(int[] nums, int val) {// 暴力法int result = nums.length;int i = 0;while (i   
class Solution {    public int removeElement(int[] nums, int val) {// 双指针法之交换int i = 0, j = nums.length - 1;int result = nums.length;while (i