前言

近期在学习大学的CS课程，接触到了一道算法题。
原题目是用C语言写的，主要考察线性查找与二分查找。

题目地址：https://www.onlinegdb.com/Hysxkv75D

线性查找 (顺序查找)

线性查找，非常简单的一种查找思路，一般就是从头(从尾)开始查，直到查询到符合条件的值。

let list = [1,2,3,4,5,6,7,8,9]
let target = 5;

for(let i=0;i<list.length;i++){
    if(list[i] === target){
        console.log('ok')
    }
}

优点: 代码写起来非常容易。
缺点: 显而易见的，这个搜索算法在数据量大的时候是非常不方便的，无法快速有效的查找到目标值。

二分查找 (折半查找)

二分查找，查找过程就是先确定一个区间，然后逐步减小范围去找。
二分查找只适用于排序好的数组

基本思路：

1.从数组中间开始找  
2.比较大小，确定下一个区间(向左or向右)  
3.与新的区间中间的值进行比较  
4.重复2-3的流程，直到找到满意的值为止。  

代码

let list = [1,2,3,4,5,6,7,8,9]
let target = 0;
let left = 0;
let right = list.length-1;
let targetIndex = -1;
while(left<=right){
    mid = Math.floor((left+right)/2)
    if(target<list[mid]){
        // 目标值小于mid，代表目标值在左边的区间。[left,mid-1]
        right = mid - 1;
    }else if(target > list[mid]){
        // 目标值大于mid,代表目标值在右边的区间。[mid+1,right]
        left = mid + 1;
    }else{
        // 就是查找到了值
        targetIndex = mid;
        break;
    }
}
console.log(targetIndex);  
//Todo: 利用递归解决问题

补充

基本就是区间的缩放，比较的值大了，区间在左边，比较的值小了，区间在右边。(数组从小到大的排序)
所以只要理解了区间的变化就能理解二分查找。
生活中最经典的应用，就是猜数。

优点：这个查找大大减少了比较的次数，提高了查找的效率。在数据量较大的情况下，效果显著。
缺点：只适用与排序好的数组。