【前端算法】折半查找

1、折半查找的原理
  折半查找用于对排好序的数组进行查找。其原理是：从数组的中间元素开始，与要查找的元素进行比较，如果相等，则中间元素为查找元素；如果大于中间元素，则在大于中间元素的那半部分数组中进行查找；如果小于中间元素，则在另一半数组中查找，如果没有，则跳出查找过程，并返回提示信息。
2、实现

function binarySearch (arr) {
    var len = arr.length;
    if(len == 1) return arr[0];//数组中只有一个数，则返回当前值

    // arr[0] * arr[len - 1] > 0 表示数组中的数全为负数或者全为整数
    if(arr[0] * arr[len - 1] >= 0) {
        if(arr[0] >= 0) {
            return arr[0];
        } else if(arr[len - 1] < 0) {
            return arr[len - 1];
        }
    }

    // arr[0] * arr[len - 1] < 0 表示数组中有正有负
    if (arr[0] * arr[len - 1] < 0) {
        var low = 0,
            high = len -1,
            mid = Math.floor((low + high) / 2);

        var midValue = Math.abs(arr[mid]);
        while (low <= high) {
            if(midValue < Math.abs(arr[mid - 1]) && midValue < Math.abs(arr[mid + 1])) {
                // 如果当前数值的绝对值比与他相邻的两个数据的绝对值都小，则该值为绝对值最小的值。
                return arr[mid];
            } else {
                if(midValue < Math.abs(arr[mid - 1]) && midValue > Math.abs(arr[mid + 1])) {
                    // 如果当前数值的绝对值小于左边相邻数据的绝对值，但是大于右边相邻数据的绝对值，则应该在右边寻找最小值
                    low = mid + 1;
                    mid = Math.floor((low + high) / 2);
                    midValue = Math.abs(arr[mid]);
                } else if (midValue > Math.abs(arr[mid - 1]) && midValue < Math.abs(arr[mid + 1])) {
                    // 如果当前数值的绝对值大于左边相邻数据的绝对值，但是小于右边相邻数据的绝对值，则应该在左边寻找最小值
                    high = mid - 1;
                    mid = Math.floor((low + high) / 2);
                    midValue = Math.abs(arr[mid]);
                }
            }
        }
    }
}

var arr = [0, 4, 7, 10];
var minValue = binarySearch(arr);
console.log(minValue);