说到二分查找很多人都是耳熟能详，这个算法基本是每个工科生（不仅仅是计算机相关专业）的必备知识点，在各种算法的题目中出现的频率也是极高的。然而很多考题并不会简简单单的去让你实现是个二分算法，而是通过各种变形来考验同学们对二分查找算法的理解程度，比如在在排序数组中查找元素的第一个和最后一个位置以及数组中的第K个最大元素这两道题里面就要用到二分搜索来寻找边界点和逼近最后的正确答案。我猜大多数人可能和我以前一样也是仅仅大概知道二分搜索这个东西并且能够简单实现，但是对于二分搜索的变形并不清楚。这篇文章将从最简单的二分查找开始讲起，然后用两个简单的二分搜索的变形的题目来加深对二分法的理解，希望能够让大家透彻的理解二分搜索这个重要的算法。

在计算机科学中，二分搜索，也称为半间隔搜索、对数搜索或二分截断，是一种搜索算法，用于查找排序数组中目标值的位置。二分搜索将目标值与数组的中间元素进行比较。如果它们不相等，则消除目标不能位于其中的那一半，并在剩余的一半上继续搜索，再次将中间元素与目标值进行比较，并重复此过程直到找到目标值。如果搜索以其余一半为空结束，则目标不在数组中。

在最坏的情况下，二分搜索的时间复杂度为 O ( l o g N ) O(logN) O(logN)，其中 N N N为有序数组的长度。有专门为快速搜索而设计的专用数据结构，例如哈希表，可以比二分搜索更有效地进行搜索。但是，二分搜索可用于解决范围更广的问题，例如，在数组中查找相对于目标数字的下一个最小或下一个最大的元素。

与其空讲不如直接用一个题目来演示，这是LeetCode第704题二分查找

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

示例1：

输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4

示例2：

输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1

这是最基本的二分搜索，看到这道题，几乎本能地写下了答案：