前言：本篇文章继续分享一种新的算法——二分查找。
一.二分查找
给定一个
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
按照一般的方法去解决上述题目，我们的第一想法肯定是将数组从头到尾遍历一遍，每个值都跟target进行一次比较，从而判断其是否存在于数组中。
此方法虽然简单，但是在最差的情况下，需要进行n次循环，即时间复杂度为O(N)，如果说在数据量很大的前提下，这样做的速度反而是非常慢的。
但是有了数组已经有序（升序）的前提，所以为了降低时间复杂度，引出二分查找的概念：
取一组数据的中间值与target进行比较，如果相等，就直接返回；
如果中间值比target小，那么数组中的目标值就一定在中间值的右边；
如果中间值比target大，那么数组中的目标值就一定在中间值的左边；
通过中间值的方法，不断将数组拆分成两半，便可以使其中一半不满足条件的数据直接舍弃，无需在进行判断，如此以来的时间复杂度变为O(logN)。
下面来看具体代码：
int search(vector<int>& nums, int target) {
int left = 0,right = nums.size() - 1;
while(left <= right)
{
int midnum = left + (right - left) / 2;
if(nums[midnum] == target)
{
return midnum;
}
else if(nums[midnum] > target)
right = midnum - 1;
else
left = midnum + 1;
}
return -1;
}二分查找，需要定义两个指针left和right，分别管理要处理的数据的两端，起始时为整个数组的两端。
随后我们需要得出中间值，求中间值有一个细节，如果我们使用(right + left) / 2的方式去求算中间值，那么当left和right均接近于INT_MAX时，就会发生数据越界，所以我们采用上述代码的方式更加稳妥。
随后进行比较，当中间值和target相等时，遍返回中间值下标；如果中间值比target大，则说明目标值在中间值的左边，此时更新right，反之则更新left，取半查找。
直到找到数据，或者left > right，即数组中不存在target时，循环方可结束。
值得注意的是，二分查找并不局限于有序的数组，凡是能够通过某种规律将数据不断分成两半的，均可使用二分查找算法。
二.x的平方根
给定一个非负整数
x，计算并返回x的平方根，即实现int sqrt(int x)函数。正数的平方根有两个，只输出其中的正数平方根。
如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
示例 1:
输入: x = 4 输出: 2示例 2:
输入: x = 8 输出: 2 解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2
本题也是一道相对简单的题，因为我们无法使用平方根函数直接解题，所以想要得到一个数的平方根，我们必须从1开始，算每个数的平方，直至算到x的平方，判断是否有一个数的平方为x。
这其实和从一个升序数组中找一个值是一样的，所以本题为了降低时间复杂度，我们需要采用二分查找的算法：1~x的中点值的平方是否为x作为判断二分条件，随后比较大小进行二分。
int mySqrt(int x) {
if(x == 0)
return 0;
int left = 1, right = x;
while(left < right)
{
long long mid = left + (right - left + 1) / 2;
long long sum = mid * mid;
if(sum > x)
right = mid - 1;
else
left = mid;
}
return left;
}但是本题有一个特殊情况，因为一个非负整数的平方根不一定也是一个整数，所以我们要取其取余后的整数部分，也就是说实际要求的整数比其平方根要小。
所以在进行区间截取时，我们需要进行改动， 因为结果小于等于目标值都有可能，所以我们需要将<=的情况放在一起判断。并且当left变动时，不能再取mid+1，因为有可能mid正好就是那个取余后的整数。
同样，我们求中间节点的方法也需要进行优化：
实际上除了第一个题目中：left + (right - left) / 2这个求中的的方法外，还有一种方法：
left + (right - left + 1) / 2
那么多的这个＋1，会有什么影响呢？？？
首先，当从left到right有奇数个数据时，使用这两种方法，所求mid均为中间值。
但是当从left到right有偶数个数据时，前者所求数据为中间值的左边，而后者则为中间值的右边。
这又会产生什么影响？？?
当我们要判断的数据只剩两个时，如果采用 left + (right - left) / 2的方式求中点，当遇到判断结果要让left = mid时，left就会一直等于mid，永远不可能大于等于right，这样就会造成死循环。
同理，如果采用 left + (right - left + 1) / 2的方式求中点，当遇到判断结果要让right = mid时，同样会造成死循环。
所以当出现该情况时，我们只需将上述两种求中点的方法进行交换即可避免死循环。
三.山峰数组的峰值索引
符合下列属性的数组
arr称为 山峰数组（山脉数组） ：
arr.length >= 3- 存在
i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]给定由整数组成的山峰数组
arr，返回任何满足arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]的下标i，即山峰顶部。
示例 1：
输入：arr = [0,1,0] 输出：1示例 2：
输入：arr = [1,3,5,4,2] 输出：2
题目还是很容易理解的，就是在数组中找到最大的一个数，并返回其下标，该数字大于其左边的数单调递增，右边的数单调递减。
我们可以通过直接遍历数组的方法去找这个数，当某数字比它的后一个数大时，即为答案。但是如果该数字为最后一个数，那我们就需要遍历整个数组，时间复杂度为O(N)。
所以为了优化时间复杂度，虽然这道题不是一个有序的数组，但我们依然可以采用二分查找。
在该数组中，某个数不是比它的前一个数大，就是比它的前一个数小，所以我们可以依此为判断条件：
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0,right = arr.size() - 1;
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(arr[mid] < arr[mid - 1])
right = mid - 1;
else
left = mid;
}
return left;
}如果mid < mid - 1，说明mid在山的右侧，此时山峰在左半区，所以right左移；当mid >= mid - 1时， 此时mid在山的左半边，山峰则在右半区，left右移，但是因为山峰是最大的数字，所以此时mid也可能是山峰，所以left的移动不能超过mid。
mid的计算方法则需按照在第二题中分享的方法进行考虑。
总结
二分查找算法适用于能够将数据按照某个条件不断分为两部分，并逐渐缩短数据范围从而寻找目标值的情况，数据并非需要严格有序。
