二分查找可以有几种写法：

  • 闭区间
  • 开区间
  • 半开半闭区间（左开右闭/左闭右开）

所谓开闭区间，指的是二分查找中的left和right的值，如果取值在数组内部（大部分情况下），就可以成为闭区间，反之为开区间。

展示这三种写法，我们从一道题目开始：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

这道题就是纯粹的二分查找板子题，数组有序，数组中无重复元素。

这里使用Java进行展示，首先是闭区间写法。

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while(l <= r){
            int mid = l + (r - l >> 1);	// 防止爆int
            if(nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return nums[l] == target ? l : -1;
    }
}

由于全程需要left和right处于闭区间内，所以更新后的取值一定是mid+1或mid-1。left=right时，mid也等于right，会陷入死循环，所以要在边界条件的判断中加入=，即while(l <= r)，最后right+1也就是left为所求答案。

然后是半开半闭区间：

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n;	// 左闭右开
        while(l < r){
            int mid = l + (r - l >> 1);
            if(nums[mid] < target) l = mid + 1;
            else r = mid;
        }
        return nums[l] == target ? l : -1;
    }
}

半开半闭写法中，谁是开区间，谁更新后就要等于mid。结束时left=right，两者返回其一即可。

最后是开区间写法：

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = -1, r = n;
        while(l + 1 < r){
            int mid = l + (r - l >> 1);
            if(nums[mid] < target) l = mid;
            else r = mid;
        }
        if(r == n) return -1;	// 由于是开区间，r有可能等于nums.length，所以要特判
        return nums[r] == target ? r : -1;
    }
}

三种写法只有代码上的区别，最后答案都是一样的，选一个顺眼的写法就好。

我们来做几道扩展题，提升对二分查找的熟练度：

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

这道题要求我们在数组中找到一段等于target的子数组，返回其起点和终点的下标，如果没有返回[-1, -1]。

起始位置很好找，套用二分模板即可。

终点如何找呢？

这就要讨论不同的要求了

  • 如果要求我们寻找>= x时，就直接使用二分模板
  • 如果要求我们寻找> x时，可以将题目转化为>= x+1
  • 如果要求我们寻找< x时，可以将题目转化为(>= x) - 1
  • 如果要求我们寻找<= x某个值时，可以将题目转化为(> x) - 1 -》 (>= x + 1) - 1

要寻找终点，也就是> x的情况。

题解代码

class Solution {
    private int[] nums;

    private int lowerBound(int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int mid = l + ((r - l) >> 1);
            if(nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }

    public int[] searchRange(int[] nums, int target) {
        this.nums = nums;
        int start = lowerBound(target);
        if(start == nums.length || nums[start] != target) return new int[]{-1, -1};
        int end = lowerBound(target + 1) - 1;
        return new int[]{start, end};
    }
}

二分不止能用在有序数组中，也能用在部分有序的数组中。

比如寻找峰值：

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

这道题给定的数组是由很多部分有序的数组组成的，峰值可能有多个，我们只需要找到其中一个即可。

这道题为什么能够使用二分查找呢？

因为我们要找到一个峰值，而峰值是一定比周围两个值高的（如果是边界则为一个值），这里可以使用二分查找来逐渐逼近这个点。

由于要找峰值，target的选择可以是nums[mid+1]或nums[mid-1]。

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int mid = l + ((r - l) >> 1);
            if(mid + 1 == nums.length) return mid;	// 特殊判断，防止越界
            if(nums[mid] < nums[mid + 1]) l = mid + 1;	// 如果mid的下一个比mid大，则峰值一定在mid后面，更新l
            else r = mid - 1; 	// 反之更新r
        }
        return l;
    }
}

最后是搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

这道题给定是一个有序无重复数组经过数次旋转后得到的数组，要求我们在其中找到target并返回其下标，如果没有返回-1。

我们可以用两次二分来解决这道题，首先类似于上一道题的查找峰值，我们先使用二分找到数组中的最小值，也就是找到两段递增数组的分界点，然后比较target与数组中最后一位数last的大小，如果target比last小，则说明其在第二段递增数组中，否则在第一段。然后最相应的数组再做一次二分即可。

题解代码：

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 2;
        int last = nums[n - 1];
        while(l <= r) {
            int mid = l + (r - l >> 1);
            if(nums[mid] > last) l = mid + 1;
            else r = mid - 1;
        }
        if(target <= last){
            r = n - 1;
            while(l <= r) {
                int mid = l + (r - l >> 1);
                if(nums[mid] < target) l = mid + 1;
                else r = mid - 1;
            }
            if(l == nums.length) return -1;
            return nums[l] == target ? l : -1;
        } else {
            r = l - 1;
            l = 0;
            while(l <= r) {
                int mid = l + (r - l >> 1);
                if(nums[mid] < target) l = mid + 1;
                else r = mid - 1;
            }
            return nums[l] == target ? l : -1;
        }
    }
}

在寻找低谷时，我们将比较对象定为last，这是因为我们要寻找最小值，如果mid比last要大，则说明数组一定被分割过并且mid在最小值左侧，移动left，反之移动right。并且由于我们的比较对象是last，所以二分时不需要考虑它，r直接定为n-2。