开juǎn有益系列（一）——Binary search（二分查找/折半查找算法）

想要在国内竞争互联网岗位，我们就必须接受现实，开卷!
本文章基于Leetcode 704. 二分查找以及以下题目编写。

Binary search（二分查找法），又名折半查找，是面试题中一个较为热门的考题类，在国内外的很多面试过程中都有出现，而代码随想录也将其作为基础算法进行讲解，说明其确实是一个适合大部分人刷题入门的一个算法门类。

首先看一下其经典题目704. 二分查找

新入门的萌新可能一下就看出端倪：一眼丁真，鉴定为暴力破解，自己遍历一遍就完事
那当然也是可以解决的，就像没有冒泡解决不了的排序一样
但是这并不是我们的目的（当然面试官看到这里或许已经达到了目的并给你划了个叉）

简单的需求往往伴随着多种解决方法，但这个题目为你划定了最优解——二分查找法

**何为二分查找？**可以看看下面这个案例，此案例目标是在此数组中查找到37，上面是二分查找法，而下面是线性查找（也就是所谓的暴力破解法），其动画就可以明显看出其时间复杂度的差距，这也是为什么我们要学习数据结构与算法的原因（当然更多的原因是为了面试拿更高的工资）

回想到Leecode 704 其入参是一个升序数组nums[],以及一个目标值target，出参则是一个索引或者是空（-1）
完全符合此图的演示过程。

首先定义两个指针初始化为索引最高位（high）与最低位（low）

		int low = 0;
        int high = nums.length - 1;//这里是因为索引从0开始，但是x.length是从1开始计算的
1
2

之后考虑其循环体的编码逻辑，其题目解决有两种情况：
1.成功寻找到目标数字并返回下标
2.遍历全数组未找到对应目标值并返回-1
而条件1未实现时达成条件2
可知其循环判断条件为当low>high时结束循环（如果写在while里循环条件就是low<=high）
于是可得循环体

		int low = 0;
        int high = nums.length - 1;//这里是因为索引从0开始，但是x.length是从1开始计算的
        while(low <= high){
        //TODO
        }
1
2
3
4
5

由上方动图可看出其mid是随high与low动态变化的，也就是保持其high与low的中位
于是计算mid的过程应当写入循环体中

		int low = 0;
        int high = nums.length - 1;//这里是因为索引从0开始，但是x.length是从1开始计算的
        while(low <= high){
        	int mid = (low + high)/2;
        	//TODO
        }
1
2
3
4
5
6

在循环体中判断情况1（成功寻找到目标数字并返回下标）的条件，因为在查找的过程中随时都可能找到目标值

		int low = 0;
        int high = nums.length - 1;//这里是因为索引从0开始，但是x.length是从1开始计算的
        while(low <= high){
        	int mid = (low  + high)/2;
        	if(nums[mid] == target){
                return mid;//return后直接中断函数执行
            }
        	//TODO
        }
1
2
3
4
5
6
7
8
9

下方就要考虑high与low两个指针移动的过程了，由动图可看出当nums[mid]小于target的时候，low指针会由原来的位置变成原来的mid+1，而大于时则是high变为mid-1（对应动图的第一步以及第二步）

于是我们可以完善以下代码

class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;//这里是因为索引从0开始，但是x.length是从1开始计算的
        while(low <= high){
        	int mid = (low + high)/2;
        	if(nums[mid] == target){
                return mid;//return后直接中断函数执行,达成情况1
            }
            if(nums[mid] > target){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        return -1;//此处循环体外补上遍历结束后未找到目标值的情况2
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

接下来的部分看周末休息的时候补上，目前还在上班就先不摸了
//TODO

参考文献：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#_704-%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE