二分查找

二分查找在做算法题的时候经常使用到，一般会用于排序后的数组中的查找目标元素

二分查找的核心思想是「减而治之」，即「不断缩小问题规模」。

涉及到三种情况

（1）无重复数据的已排序数组寻找目标元素

（2）有重复数据的已排序数组寻找目标元素第一次出现的位置

（3）有重复数据的已排序数组寻找目标元素最后一次出现的位置

二分查找中的while写法

使用：

（1）while(left < right) ： 这样写的好处是退出循环的时候 left == right，这样的话，在返回的时候不用考虑是返回left还是right 的问题

（2）while(left <= right) ：这样写的好处是退出循环的时候 left == right + 1，这样的话，在返回的时候，就要考虑一下left的值是啥，right的值是啥

下面对这三种情况分别进行一个算法讲解与介绍：

1、无重复数据的已排序数组寻找目标元素

Leetcode 相关题目：二分查找

（1）利用while(left <= right)

class Solution {
	// nums是已经排序好的数组
	// target是目标数字
	// 寻找数组中目标数字出现的位置，没有则返回-1
    public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target){
                return mid;
             // 若该中间值比目标元素大，则找[left , mid - 1]
            }else if(nums[mid] > target){
                right = mid - 1;
            // 若该中间值比目标元素大，则找[mid + 1, right]
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }
}

（2）利用while(left < right)

public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        // 特判
        if (nums[len - 1] < target) {
            return -1;
        }
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 严格小于 target 的元素一定不是解
            if (nums[mid] < target) {
                // 下一轮搜索区间是 [mid + 1, right]
                left = mid + 1;
            } else {
                // 下一轮搜索区间是 [left, mid]
                right = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }

LeetCode 搜索插入位置

// 第一种 ： while(left <= right)
public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        if(nums[right] < target){
            return len;
        }
        while(left <= right){
            int mid = (right - left ) / 2 +  left;
            if(nums[mid] == target){ 
                return mid;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
// 第二种 ： while(left < right)
     public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        if(nums[right] < target){
            return len;
        }
        while(left < right){
            int mid = (right - left ) / 2 +  left;
            if(nums[mid] >= target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left ;
    }

2、有重复数据的已排序数组寻找目标元素第一次出现的位置

Leetcode 相关题目：在排序数组中查找元素的第一个和最后一个位置

（1）利用while(left <= right)

// nums是已经排序好的数组
// target是目标数字
// 寻找数组中目标数字第一次出现的位置，没有则返回-1
private int findFirstPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                // ① 不可以直接返回，应该继续向左边找，即 [left..mid - 1] 区间里找
                right = mid - 1;
            } else if (nums[mid] < target) {
                // 应该继续向右边找，即 [mid + 1, right] 区间里找
                left = mid + 1;
            } else {
                // 此时 nums[mid] > target，应该继续向左边找，即 [left..mid - 1] 区间里找
                right = mid - 1;
            }
        }
        // 此时 left 和 right 的位置关系是 [right, left]，注意上面的 ①，此时 left 才是第 1 次元素出现的位置
        // 因此还需要特别做一次判断
        if (left != nums.length && nums[left] == target) {
            return left;
        }
        
        return -1;
    }

图解如下：

（2）利用while(left < right)

 private int findFirstPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                // 应该继续向右边找，即 [mid + 1, right] 区间里找
                left = mid + 1;
            } else {
                // 此时 nums[mid] >= target，应该继续向左边找，即 [left..mid] 区间里找
                right = mid ;
            }
        }
        // 此时 left 和 right 的位置关系重合的
        // 因此还需要特别做一次判断
        if (left != nums.length && nums[left] == target) {
            return left;
        }
        return -1;
    }

3、有重复数据的已排序数组寻找目标元素最后一次出现的位置

Leetcode 相关题目：在排序数组中查找元素的第一个和最后一个位置

// nums是已经排序好的数组
// target是目标数字
// 寻找数组中目标数字最后一次次出现的位置，没有则返回-1
private int findLastPosition(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            // 只有这里不一样：不可以直接返回，应该继续向右边找，即 [mid + 1, right] 区间里找
            left = mid + 1;
        } else if (nums[mid] < target) {
            // 应该继续向右边找，即 [mid + 1, right] 区间里找
            left = mid + 1;
        } else {
            // 此时 nums[mid] > target，应该继续向左边找，即 [left, mid - 1] 区间里找
            right = mid - 1;
        }
    }
    // 此时 left 和 right 的位置关系是 [right, left]，此时 right 才是最后一次元素出现的位置
    // 因此还需要特别做一次判断
    if (right >= 0 && nums[right] == target) {
            return right;
    }
    return -1;
}

图解如下：