算法系列之二分查找

二分查找也称折半查找（Binary Search），二分查找针对的是有序的线性表，并且线性表要采用顺序存储结构，满足这个条件的就是数组这种结构了。

查找过程

首先，假设表中元素是按升序排列，将表中间位置的值与查找目标值字比较，如果两者相等，则查找成功；否则利用中间位置将表分成前、后两个子表，如果中间位置的值大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。 - 百度百科

简单二分查找

简单的二分查找, 只要查到等于目标值的索引, 代码非常直接简单

function bSearch(arr, target) {
    let left = 0 //左指针
    let right = arr.length - 1 //右指针
    while (left <= right) {
        let mid = (right - left) >> 1 + left
        if (arr[mid] === target) {
            return mid
        } else if (arr[mid] < target) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

复制代码

三个容易出错的地方

1. 循环退出条件，注意是 left<=right ，而不是 left < right
2. mid的取值 实际上， mid=(left+right)/2 这种写法是有问题的。因为如果left和right比较大的话，两者之 和就有可能会溢出。改进的方法是将mid的计算方式写成 left+(right-left)/2 。更进一步，如果 要持性能优化到扱致的话，我们可以将这里的除以2操作转化成位运算 left+((right-left)>>1)
3. left和right的更新 left=mid+1 , right=mid-1 。注意这里的+1和-1 ,如果直接写成left=mid或者right=mid , 就可能会发生死循环。比如，当right=k , left=k时，如果a[k]不等于target, 就会导致死循环。

二分查找的变形

上面的简单二分查找是有序且不重复的数组，我们现在来考察有序但是有重复数据的数组 我们来看看四个变形问题

1. 查找第一个等于目标值的元素索引

function bSearch1(arr, target) {
    let left = 0 
    let right = arr.length - 1
    while (left <= right) {
        let mid = (right - left) >> 1 + left
        if (arr[mid] === target) {
            if (mid === 0 || arr[mid - 1] !== target) {
                return mid
            } else {
                right = mid - 1
            }

        } else if (arr[mid] < target) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}
复制代码

注意现在数组里面有重复的元素，所以当满足 arr[mid] === target , mid不一定是第一个等于目标值的元素, 因此还需要一个条件分支判断 mid === 0 || arr[mid - 1] !== target ， 如果mid是0，那么是第一个元素，肯定满足条件，或者当前位置的前一个元素不等于目标值，那么这个位置一定就是我们要找第一个等于目标值的元素的索引 如果不满足这个条件，说明这个位置前面还有等于目标值的元素，那么需要更新右边的指针 high = mid - 1 ;

变形1理解了，后面的三个变形问题也是同样的思路, 聪明的你肯定可以举一反三

2. 查找最后一个等于目标值的元素索引

function bSearch2(arr, target) {
    let left = 0
    let right = arr.length - 1
    while (left <= right) {
        let mid = (right - left) >> 1 + left
        if (arr[mid] === target) {
            if (mid === arr.length - 1 || arr[mid + 1] !== target) {
                return mid
            } else {
                left = mid + 1
            }

        } else if (arr[mid] < target) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}
复制代码

3. 查找第一个大于等于目标值的元素索引

function bSearch3(arr, target) {
    let left = 0
    let right = arr.length - 1
    while (left <= right) {
        let mid = (right - left) >> 1 + left
        if (arr[mid] >= target) {
            if (mid === 0 || arr[mid - 1] < target) {
                return mid
            } else {
                right = mid - 1
            }
        } else {
            left = mid + 1
        }
    }

}
复制代码

4. 查找最后一个小于等于目标值的元素索引

function bSearch4(arr, target) {
    let left = 0
    let right = arr.length - 1
    while (left <= right) {
        let mid = (right - left) >> 1 + left
        if (arr[mid] <= target) {
            if (mid === arr.length - 1 || arr[mid + 1] > target) {
                return mid
            } else {
                left = mid + 1
            }

        } else {
            right = mid - 1
        }

    }
}
复制代码

leetcode相关题解

最后来看看leetcode的33题

题目描述：

假设按照升序 排序 的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 你可以假设数组中不存在重复的元素。 你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1 搜索旋转排序数组, 要求时间复杂度是O(logn)

解题思路：

将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环直到找到目标值或者左边界超出右边界，退出循环

规律： 中间值比最右值小，则右半部有序递增 中间值比最右值大，则左半部有序递增

代码

function search(nums, target) {
    let left = 0
    let right = nums.length - 1
    let mid
    while (left <= right) {
        mid = left + ((right - left) >> 1) // 注意位运算符打括号
        if (nums[mid] == target) {
            return mid
        }
        //右半部有序递增
        if (nums[mid] < nums[right]) {
            if (nums[right] >= target && nums[mid] < target) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        } else {
            if (nums[left] <= target && nums[mid] > target) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
    }
    return -1
}
复制代码

这个算法也可以用递归实现，我用递归写的代码在leetcode上通不过，老是报栈溢出错误，所以我这里就不贴了，有兴趣的可以尝试写一下递归代码