704. 二分查找

题目链接

• 使用条件：
  1. 数组有序
  2. 无重复元素
• 写法：
  根据搜索区间边界是左闭右开还是左闭右闭分为两种写法：
  • 左闭右开
    区间右侧不包括在区间内，在写代码的时候需要时刻牢记这一点，否则很容易出错。

class Solution {
    public int search(int[] nums, int target) {
        // 左闭右开，重合无意义
        int left = 0;
        int right = nums.length;  // 开区间 #1
        int middle;
        while (left < right) {      // 开区间 #2
            middle = left + (right - left) / 2;     // 防止直接运算(left + right)导致溢出
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else if (nums[middle] > target) {
                right = middle;  // 开区间 #3
            }
        }
       return -1;
    }
}

• 左闭右闭
  区间右侧包括在区间内，因此写法上与左闭右开有几处区别

class Solution {
    public int search(int[] nums, int target) {
        // 左闭右闭，重合有意义
        int left = 0;
        int right = nums.length - 1;  // 闭区间 #1
        int middle;
        while (left <= right) {      // 闭区间 #2
            middle = left + (right - left) / 2;     // 防止直接运算(left + right)导致溢出
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else if (nums[middle] > target) {
                right = middle - 1;  // 闭区间 #3
            }
        }
       return -1;
    }
}

35.搜索插入位置

题目链接
本题满足二分法使用的两个前置条件：有序数组，无重复元素，因此可以使用二分法降低时间复杂度。
分析题目可知元素可能出现如下情况：

• 元素在数组内
• 元素不在数组内
  • 元素比数组内任意一个元素小
  • 元素处于数组内某两个元素之间
  • 元素比数组内任意一个元素大

元素在数组内的情况与普通二分查找一致，不赘述。
元素不在数组内时，考虑满足while循环条件的最后一次比较。以左闭右开为例，进行满足while循环条件的最后一次比较时，middle = left。若：

• nums[middle] > target，则right = middle，此时target应该插入的位置为middle，也就是left或者right
• nums[middle] < target，则left = middle + 1，此时target应该插入的位置为middle + 1，也就是left或者right

综上，当元素不在数组内时，应该插入的位置为left或right（区间定义为左闭右开时）。
同理可得，当区间定义为左闭右闭时，元素应该插入的位置为left或right + 1

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 左闭右开
        int left = 0;
        int right = nums.length;
        int middle;

        while (left < right) {
            middle = left + (right - left) / 2;
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        return left;
        // return right;
    }
}

27. 移除元素

题目链接
本题使用双指针以在一个for循环内完成两个for循环的工作。
初始状态下，快慢指针指向同一个元素。当快指针第一次遇到特定元素时，慢指针指向的也是这个元素，因此需要让快指针指向下一个元素，判断是否为特定元素，直到快指针指向非特定元素。此时，慢指针还留在该特定元素位置处。使用快指针指向的非特定元素覆盖慢指针指向的特定元素，之后慢指针指向下一个元素。
在此逻辑下，一个for循环即可完成题目要求。

class Solution {
    public int removeElement(int[] nums, int val) {
        // 双指针
        int slowIndex = 0;
        int fastIndex;
        for (fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        // while循环也能写出一样的效果，但没必要
        // while (fastIndex < nums.length) {
        //     if (nums[fastIndex] != val) {
        //         nums[slowIndex] = nums[fastIndex];
        //         slowIndex++;
        //         fastIndex++;
        //     } else {
        //         fastIndex++;
        //     }
        // }
        return slowIndex;
    }
}