算法系列之二分查找

733 阅读5分钟

二分查找

二分查找也称折半查找(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上通不过,老是报栈溢出错误,所以我这里就不贴了,有兴趣的可以尝试写一下递归代码