704. 二分查找

文章学习链接：704.二分查找
此题二分法前提条件：
1. 数组有序
2. 无重复元素
区间定义：循环不变量原则，这点非常重要
1. 左闭右开：[left, right)（本人使用）
2. 左闭右闭：[left, right]
此题代码：

class Solution {
    public int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;					//注意这里，因为target直接与mid位置值比较，
                								//所以mid就不在范围之内，因此左边界要加1
            } else if (nums[mid] > target) {
                right = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

35. 搜索插入位置

文章学习连接35. 搜索插入位置
题目分析：
1. 本次是在二分查找的基础上进行，因此代码框架为二分查找框架
2. 与二分查找不同的是，该题需要返回插入的位置，插入位置有三种情况
  1. 数组前
  2. 数组中
  3. 数组后
3. 要注意区间不变量的问题，本人目前主要使用左闭右开的区间不变量
代码：

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (target < nums[0]) return 0;
        if (target > nums[nums.length - 1]) return nums.length;
        /*数组前、数组后这两种情况，在下述代码中可被替代*/
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return right;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

文章学习链接
题目分析：
1. 目的是查找范围，及查找左边界和右边界
2. 构造寻找左边界、有边界的函数，寻找边界这里应用到二分法，但与二分查找不同的是此题存在重复元素。
3. 此题最难的部分就是，为什么RightBorder = left（为例），关于为什么是用left来更新右边界，作者的理解是left是不断向右靠近的，那么当其不能继续右靠的时候，就是右边界，左边界同理。
代码：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int RightBorder = getRightBorder(nums, target);
        if (leftBorder == -2 || RightBorder == -2) return new int[]{-1,  -1};
        if (RightBorder - leftBorder > 0) return new int[]{leftBorder, RightBorder - 1};
        return new int[]{-1, -1};
        
    }
    private int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        int leftBorder = -2;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] >= target) {
                right = mid;
                leftBorder = right;
            } else {
                left = mid + 1;
            }
        }
        return leftBorder;
    }
    private int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        int RightBorder = -2;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] <= target) {
                left = mid + 1;
                RightBorder = left;
            } else {
                right = mid;
            }
        }
        return RightBorder;
    }
}

27. 移除元素

文章学习链接27.移除元素
本题所用方法：
1. 暴力法（也能过）
2. 双指针法（重点）
此题代码：

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        int fast = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == val) {
                fast++;
                continue;
            }
            nums[slow] = nums[fast];
            fast++;
            slow++;
        }
        return slow;
    }
}

class Solution {
    public int removeElement(int[] nums, int val) {
        // 快慢指针
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}