二分查找算法

大大源码 • 2023年5月18日 pm11:43 • 其他

一、什么是二分查找？

周一早上，天刚蒙蒙亮，程序员小王来到公司，打开电脑，准备一天充实的工作，测试妹子余光中看见小王打开电脑，高兴的跑过来，问小王，今天发型好飘逸呀，测试妹子心想，小王之前没头发，今天怎么有头发了，肯定是植发去了，嘿嘿。小王，嘴角微微上扬优雅的说，周末出去玩，看见假发打折，所以入手了一头，小王说，这个假发不到100块钱，你猜猜多少钱呀，测试妹子说50，小王说低了，再猜，测试妹子说80，小王说高了，再猜，测试妹子说70，小王说，你真聪明，猜对了，就是70，测试妹子在小王的夸赞中高兴的离开了。

小王跟测试妹子玩猜猜游戏其实就是二分查找的思想，二分查找就是在一组有序元素列表中通过对半查找，来快速锁定目标数据。

二、二分查找的运行时间

从组数[1,3,4,5,7,8,10,12] 需要找出target=10 在数组中位置，我们采用一下两种方法就行对比。

第一种方法：遍历数据，找出10在数据中的位置，需要7次，如果目标数在数组的最后一位，最差需要遍历8次，也就是说最差我们需要遍历数组长度次。

第二种方法：二分查找，每次找到中间位置的元素，跟目标数作对比，如果中间元素小于目标数，left=mid+1,如果中间元素大于目标数，right=mid-1,依次类推，直到，left<=right,查找完成。如下图

找出目标元素最差需要3次。

接下来如果我们把数据量放大到10亿条数据，第一种方法最差就需要10亿次，但是二分查找只需要大概30次，这个差距是非常大的，也就是说包含n个元素的列表，使用二分查找最多需要㏒₂n次。

在算法中，算法的好坏，我们采用大O表示法，他代表在最糟糕的情况下灌入算法的数据跟时间的一个关系

第一种方法运行时间O(n),第二种方法运行时间O(㏒₂n)

三、二分查找的练习

leetcode上二分查找题目有两百多道，如果时间足够多，我们可以刷一遍，但是，最终还是要静下心来，真正理解二分查找，学会灵活应用才算是整的掌握了该算法。

35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
输入: nums = [1,3,5,6], target = 5
输出: 2
public int searchInsert(int[] nums, int target) {
     int length = nums.length;
        int left = 0;
        int right = nums.length-1;
        while (left <= right) {
           int mid = (left + right) / 2;
            if (nums[mid] < target) {
                 left=mid+1;
            }else{
               right=mid-1;
            }
        }
        return left;
    }