二分查找变形

代码1：

function binarySearch(array, value) {    var low = 0;    var high = array.length-1;    while (low <= high) {        let mid = low+((high-low)>>1);        if (array[mid] < value) {            low = mid + 1;        } else if (array[mid] > value) {            high = mid - 1;        } else {            if (mid==0||array[mid-1]!=value) return mid;            high = mid - 1;        }    }        return -1;}复制代码

前提：array是从小到大排序的 第一个等于给定值，在前面，因此high = mid -1，出口是mid==0||array[mid-1]!=value找到了第一个。

同理最后一个mid==n-1||array[mid+1]!=value, low = mid + 1;

代码3：

function binarySearch(array, value) {    var low = 0;    var high = array.length-1;    while (low <= high) {        let mid = low+((high-low)>>1);        if (array[mid] < value) {            low = mid + 1;        } else if (array[mid] >= value) {            if (mid==0||array[mid-1]

同理第4个问题：

if (array[mid] <= value) {    if (mid == array.length-1 || array[mid+1] > value) return mid;    low = mid + 1;}复制代码

总结

综上，以上二分查找变形可以解决查找数据区间，或近似值的各种问题。

如：如何快速定位出一个IP地址的归属地？（IP地址可转化为32位整数，找到最后一个小于等于指定IP的区间）

在循环有序数组中查找给定值。 如 5、7、9、10、23、1、3、4 观察该类数组的结构，可以分为两部分1，2。都是有序数组，1整体大于2.

利用二分查找思想，根据中间值判断目标值范围，再不断缩小。

function binarySearch(array, value) {    var low = 0;    var high = array.length-1;    while (low <= high) {        let mid = low+((high-low)>>1);        if (array[mid] == value) return mid;        if (array[mid] >= array[low]) { // 中点在左半部分            if (array[mid] > value && array[low] <= value) {                high = mid - 1;            } else {                low = mid + 1;            }                    } else if (array[mid] <= array[high]) { // 中点在右半部分            if (array[mid] < value && value <= array[high]) {                low =  mid + 1;            } else {                high = mid - 1;            }        }    }        return -1;    }复制代码