二分查找的三种形式

---

前言

本文主要作为自己的学习记录，解题步骤并未详细说明，关键点在注释中给予了简要说明。如有疑问，欢迎留言讨论。

---

一、经典二分查找

题目描述：在不重复有序数组（升序）中寻找目标数并返回它的下标，若没找到返回-1。
例子：[1, 2, 3]，2；返回：1。见leetcode题(704)：https://leetcode-cn.com/problems/binary-search/
上代码：

	public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) // 异常处理
            return -1;
        
        int left= 0;
        int right= nums.length - 1;
        while (left <= right) { 
        // “<=”和left、right的取值有关，上面确定了是闭区间，因此当left与right相等时，仍然需要查找一次。 
            int mid = left+ (right- left) / 2; // 防止溢出
            if (target == nums[mid])
                return mid;
            else if (target < nums[mid])
                right = mid -1;
            else if (target > nums[mid]) // 用else if可以将条件清晰的展现出来，便于将逻辑理清，也可以改为else
                left= mid + 1;
        }
        
        return -1;
    }

若完全理解，那么代码中的<=，可自行替换成<，替换后要更换其他部分代码。

二、左边界二分查找

题目描述：返回有序数组（升序）中目标数第一次出现的下标，若没找到返回-1。
例子：[1, 2, 2, 2, 3], 2；返回：1。
此处我们统一以闭区间解题。
代码如下：

	public int binarySearch(int[] nums, int target) {
        // write your code here
        if (nums == null || nums.length == 0) // 异常处理
            return -1;
        
        int left= 0;
        int right= nums.length - 1;
        // 闭区间，当左指针大于右指针时，左指针所指向的数即为目标数（目标数一定存在数组中时），此时右指针比左指针小1
        while (left <= right) { 
            int mid = left+ (right- left) / 2; // 防止相加溢出
            // 关键部分，由于寻找左边界，因此要将右指针的位置向前移，向左侧缩小区间
            if (target == nums[mid]) 
                right = mid -1;
            else if (target < nums[mid]) 
                right = mid -1;
            else if (target > nums[mid]) 
                left = mid + 1;
        }
        
        if (left >= nums.length || nums[left] != target)
            return -1; // 处理可能存在的越界情况（目标数大于所有数）以及不存在目标数情况
        return left; // 也可返回 right + 1
    }

三、右边界二分查找

右边界与左边界相似，可以在理解左边界的基础上自己实现。（参见附录）

总结

本文主要作为笔者的学习记录，需要注意的关键点在注释中予以了标注，若有错误欢迎指出。

附录

右边界代码如下：

public int right_bound(int[] nums, int target) {
        if (nums == null || nums.length == 0)
            return -1;
        
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid])
                left = mid + 1;
            else if (target < nums[mid]) 
                right = mid - 1;
            else (target > nums[mid]) 
                left = mid + 1;
        }
        
        if (right < 0 || nums[right] != target)
            return -1;
        return right;
    }