要进行二分的话肯定需要有序才可以, 如果没有顺序的话就要使他有序, 那我们可以选择排序后再进行二分查找. 有没有更好地方法呢, 有的😺, 就是边排序边二分查找
二分法和快排处理方式差不多, 都是找一个数作为基准进行处理, 二分找中间, 有时候可以并行进行会快一些

1. 数组有序的情况下

1. 递归方式

// target查询目标, arr数组, start数组下标开始位置, end数组下标结束位置
function binarySearch(target,arr,start,end) {
    // 一定要有一个递归出口, 不然找不到的时候就会报错
    if (start > end) return -1;

    var mid = parseInt(start+(end-start)/2);

    if(target===arr[mid]){
        return mid;
    }else if(target>arr[mid]){
        return binarySearch(target,arr,mid+1,end);
    }else{
        return binarySearch(target,arr,start,mid-1);
    }
}
// 输入9个元素数组
var arr = [0, 1, 5, 6, 7, 9, 15, 56, 86];
console.log(binarySearch(0,arr,0,8)); // ==> 3

2. 非递归方式推荐使用

function binarySearch(target,arr,start,end) {
    while (start <= end) {
        var mid = parseInt(start + (end - start)/2);
        if (target === arr[mid]) {
            return mid;
        } else if (target > arr[mid]) {
            start = mid +1;
        } else {
            end = mid -1;
        }
    }
    return -1;
}
// 输入9个元素数组
var arr = [0, 1, 5, 6, 7, 9, 15, 56, 86];
console.log(binarySearch(0,arr,0,8));

---

2. 数组无序的情况下

一边快排, 一边查找

// 只需要返回找没找到可以这样写, 如果需要找index就换一种方式
function binarySearch(target,arr) {
    // 只要arr长度大于0就可以继续下去
    while (arr.length > 0) {
        // 预先准备
        var left = [];
        var right = [];
        // 选择第一个元素作为基准
        var pivot = arr[0];

        // 找到了就直接返回找到的位置
        if (target === pivot) return true;


        // 从第二个元素开始进行查找
        for(var i = 1; i < arr.length; i++) {
            // 把大于基准的放在左边, 小于基准的放在右边
            arr[i] > pivot?right.push(arr[i]):left.push(arr[i]);
         }

         // 进行下一步左右子树查找
        if (target > pivot) {
            arr = right;
        } else if (target < pivot) {
            arr = left;
        }
    }
    return -1;
}
// 输入9个元素数组
var arr = [78, 56, 56,12,8,97,45,93,41];
console.log(binarySearch(97,arr,0,8));

---

「扩展知识」二维数组二分法查找

var a = [
  [1,2,7,14],
  [2,4,9,16],
  [4,7,10,19],
  [6,18,28,50]
]

假如有这么一串二维数组, 要查找其中的值是否存在, 首先需要观察, 我们要查询的数字比某一个位置例如x的数字小的话, 那么我们要查询的数字位置不可能出现在以x为行列开始的右下角区域

流程图如下:

二维数组查找流程.jpg