目录

一、基础知识
- 二分法解题思路
- 数组中删除的思路
二、题目一：704.二分查找
三、题目二：27.移除元素

一、基础知识

1.二分法解题思路

要求数组必须是有序排列，仅需要根据题目的条件去确定搜索区间。

• 第一个关键点：区间的取值。
  一般有左闭右闭，左闭右开，左开右闭三种，这个的选择不同会影响后面循环中while(left<=right)是否需要等号。
  左闭右闭
  那么需要加上“=”，此时right = nums.length - 1,是能取到右边界。
  左闭右开
  right = nums.length，此时区间是取不到右边界的元素，循环中不用加“=”。
• 第二个关键点：mid的计算方式mid=(left+right)/2和mid=left+(right-left)/2或者mid=l+(r-l)>>1，主要是根据会不会溢出来选择,选择后者则不会溢出。

2.数组中删除元素的思路

首先，需要明确数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

• 暴力解法
  使用两个for循环，一个用来遍历数组元素，一个用来更新数组元素。
• 双指针方法
  通过一个快指针和一个慢指针，完成两个for循环的工作量。要明白这里面快慢指针的作用。
  快指针：寻找新的数组元素（不是目标元素的元素都是新数组的元素）。
  慢指针：更新新数组元素的下标。

二、题目一：704.二分查找

题目链接
https://leetcode.cn/problems/binary-search/
代码
左闭右闭

var search = function(nums, target) {
    // right是数组最后一个数的下标，num[right]在查找范围内，是左闭右闭区间
    let mid, left = 0, right = nums.length - 1;
    //左闭右闭，所以要加上等号
    while (left <= right) {
        // 右移运算符>> ，运算结果是一个整数的二分之一，能代替数学上除2的运算，但是比这个运算更快，防止大数溢出。
        mid = left + ((right - left) >> 1);
        if (nums[mid] > target) {
            right = mid - 1;  //区间变成[left，mid-1]
        } else if (nums[mid] < target) {
            left = mid + 1;   // 区间变成[mid+1,right]
        } else {
            return mid;
        }
    }
    return -1;
};

左闭右开

var search = function(nums, target) {
    // right是数组最后一个数的下标+1，nums[right]不在查找范围内，是左闭右开区间
    let mid, left = 0, right = nums.length;
    //不包含最右边的那个元素，所以不用加上等号
    while (left < right) {
        // 位运算 + 防止大数溢出
        mid = left + ((right - left) >> 1);
        if (nums[mid] > target) {
            right = mid;  // 区间[left,mid)
        } else if (nums[mid] < target) {
            left = mid + 1;   //区间[mid+1,right)
        } else {
            return mid;
        }
    }
    return -1;
};

三、题目二：27.移除元素

题目链接
https://leetcode.cn/problems/remove-element/

代码
暴力解法

var removeElement = function(nums, val) {
    let newlength = nums.length;
    let j = 0;
    for(let i = 0; i < newlength; i++){
        if(nums[i] === val){
            for(j = i; j < newlength - 1; j++){
                nums[j] = nums[j+1];
            }
            i--;
            newlength--;
        }
    }
    return newlength
};

双指针解法

var removeElement = (nums, val) => {
    let k = 0;
    for(let i = 0;i < nums.length;i++){
        if(nums[i] != val){
            nums[k++] = nums[i]
        }
    }
    return k;
};