算法训练营第一天 704 .二分查找、27.移除元素

算法训练营第一天 | 704 .二分查找、27.移除元素

（ 一 ）、704 二分查找

题目链接：https://leetcode.cn/problems/binary-search/description/

解题思路：

​ 数组 nums 是有序排列的，二分查找每次都是对半查询，其实也是双指针的思想，一个 left 指向数组的第一个元素（元素的在数组中位置）， 另一个 right 指向数组的最后一个元素。取数组中间的值( mid = ( left + right ) / 2 ) 进行比较，这里的 mid 也是中间元素的坐标 ， 如果 nums[ mid ] 和传入的值 target 相等，那么说明我们找到了这个元素，则返回 mid .
​ 如果不相等，我们就进行下面的判断，if ( nums[ mid ] < target ) ,说明 target 的大小是在右半部分， 那么此时，我们将 left 移动至 mid 的前一个位置。 left =mid +1 .
相反 if ( nums[ mid ] > target ) 说明说明 target 的大小是在左半部分，同样 我们将 right 移动到mid 的后一个位置。right = mid -1 ;

重点：

循环什么时候停止：（1 . ）:找到了我们的 target 直接返回 mid

​ ( 2 .) : left <= right ,循环的终止条件，这里为什么要 取等于，如果我们直接小于就结束的话，这样 是不是就漏 掉一个元素没有比较。

当我们的循环结束之后，说明没有找到数组中不存在 target ，那么此时我们直接返回 -1 .

具体实现代码如下：

int search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
      
        while( left <= right ){
            int mid=(left+right)/2;
             if( nums[mid]==target ){
                 return mid;
             }else if( nums[mid] < target){
                 left=mid+1;
                 continue;
             }else if( nums[mid] > target ){
                 right=mid-1;
                 continue;
             }
        }
        //循环结束之后没有找到目标值
        return -1 ;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

如果还没有明白的朋友，可以看看视频版讲解（代码随想录）： 二分查找视频讲解

（ 二 ）27. 移除元素

题目链接： 27. 移除元素 - 力扣（LeetCode）

解题思路：

说明： 这里我们不使用c++ 的迭代器 （iterator）+ 库函数 eras() 直接删除的方式来实现。

这里呢我们采用的还是双指针的思路：

其实也很简单，我们定义两个变量 man , kuai ，开始都指向数组的第一个元素，然后开始循环遍历（ kuai指针来控制控制循环 ），如果 nums[ kuai ]!= val ,说明不是我们要删除的元素 ， nums[ man ]=nums[ kuai ]（用慢指针来接受），如果相等，则不做任何处理，进入下一层循环，最后循环结束之后，man( 慢指针 )的值就是我们元素的个数，直接返回。

具体代码实现:

int removeElement(vector<int>& nums, int val) {
        int kuai=0 ;
        int man=0 ;
        for(  ; kuai < nums.size() ; kuai++ ){
            if( nums[kuai] != val){
                nums[ man ] = nums[ kuai ];
                man++;
            }
        }
        return man;
    }
1
2
3
4
5
6
7
8
9
10
11

视频版讲解（代码随想录）：移除元素视频讲解