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

文章目录

• 数组理论基础
• 704. 二分查找
• • 1.解题思路
  • 2.代码
  • 三、移除元素
  • • 1.解题思路
    • 2.代码对比
    • ���结

      ---

      数组理论基础

      1.空间上连续，假如需要插入或删除元素则后续所有元素都要改变位置

      （）

      2.数组下标从0开始

      3.数组元素只能覆盖不能删除

      （）

      4.二维数组地址在C++中是连续的

      ---

      704. 二分查找

      给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

      示例 1:

      • 输入: nums = [-1,0,3,5,9,12], target = 9
      • 输出: 4
      • 解释: 9 出现在 nums 中并且下标为 4

        示例 2:

        • 输入: nums = [-1,0,3,5,9,12], target = 2
        • 输出: -1
        • 解释: 2 不存在 nums 中因此返回 -1

          1.解题思路

          在有序数组中，设置左右两个标志划定范围区间（左闭右闭、左闭右开）、不断取中心值与目标对比，折半查找

          注意区间开闭与判断条件是否等于、左右是否包含middle的关系

          闭区间移动包含middle、开区间不包含middle

          2.代码

          class Solution {//左闭右闭    public int search(int[] nums, int target) {        int left=0;         int right=nums.length-1;        int middle=0;        while(left  //左闭右闭、等号有意义、左右区间都不包含middle            middle = (left+right)/2;            if(nums[middle]target){  // 左区间                right=middle-1;            }            else if(nums[middle]// 右区间                left = middle+1;            }            else if(nums[middle] == target){                return middle;            }        }        return -1;    }}    //左闭右开    public int search(int[] nums, int target) {        int left=0;         int right=nums.length;        int middle=0;        while(left    //左闭右开时等号无意义            middle = (left+right)/2;            //middle = left + ((right - left)  1);            if(nums[middle]>target){  // 左区间，右边界包含middle                right=middle;            }            else if(nums[middle]// 右区间，左边界不包含middle                left = middle+1;            }            else if(nums[middle] == target){                return middle;            }        }        return -1;    }}//暴力    public int removeElement(int[] nums, int val) {        int n=nums.length, i=0, j=0;        for(i=0; i            if(nums[i]==val){                                for(j=i+1; j                    nums[j-1]=nums[j];                }                i--;// 后面元素往前了一位                n--;// 总数减一            }                    }        return n;    }}// 双指针法（快慢指针法）    public int removeElement(int[] nums, int val) {        int slow = 0, fast = 0;        for(fast = 0; fast            if(nums[fast] != val){                nums[slow]=nums[fast];                slow++;            }        }        return slow;    }}