**可以二分的必要条件：有序。二分查找代码看起来简单，如果不理清边界条件可能需要调试很久。想要写出正确二分代码的重点在于关注循环不变量。**二分查找有三种写法，不同的写法有不同的循环结束条件、不同的 left、right 初始值以及不同的返回值。

二分的目的就是在整个搜索区间（即数组中所有的元素）中寻找一个符合条件的元素，搜索区间即 left 和 right 之间未搜索的元素，left 左边 right 右边的元素均为已搜索过的区间，每次搜索的目的就是将未搜索区间的一半元素划分到已搜索区间中，直至最后未搜索区间为空。

循环不变量即为 left 的左侧和 right 的右侧，left 左侧的元素均为小于 target 的，right 的右侧均为大于 target 的。

正常的二分查找

leetcode 35 题

现在给你一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

分析题目可知，如果数组中存在和 target 相等的值，则返回对应的下标，如果不存在则返回第一个大于 target 的下标。

闭区间写法 [left, right]

• 初始值

  为保证在查找过程中不遗漏元素，left 和 right 的初始值应该为数组的第一项和最后一项

• 结束条件

  只有当 left > right 时，[left, right] 这个闭区间才不包含任何元素

• left 和 right 的变化

  每次循环时，下标为 mid 的元素都参与过了，为了避免无限循环，left 和 right 在下次循环中应该取 mid 都下一位，即加一后者减一

• 返回值

  关注循环不变量，left 左边永远小于 target，right 右边永远大于 target

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let l = 0, r = nums.length - 1 // 初始值
    while (l <= r) { // 当 l <= r 时，[l, r] 中仍有元素为搜索
        const mid = (l + r) / 2 | 0
        if (nums[mid] == target)
            return mid
        else if (nums[mid] < target)
            l = mid + 1
        else 
            r = mid - 1
    }
    return r
};

半开半闭写法 [left, right)

• 初始值

  为保证在查找过程中不遗漏元素，left 为闭区间所以取0即可，right 为开区间，为了不遗漏元素，应该取最后一项右侧即 nums.length

• 结束条件

  当 left 和 right 相等时，[left, right) 这个区间中已经不包含任何元素了