算法入门——二分查找

二分查找(Binary Search)

1. 定义

折半查找

2. 数据要求

线性表、有序(哪头大或哪头小)(例如:排序后的数组)

3. 算法

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null) {
            return -1;
        }

        int start = 0;
        int end = nums.length - 1;
        while(start <= end) {
            int mid = start + (end - start) / 2;// 防止计算时溢出
            if(target > nums[mid]) {
                start = mid + 1;
            } else if(target < nums[mid]) {
                end = mid - 1;
            } else
                return mid;
        }

        return -1;
    }
}

可用递归实现二分查找

mid = start + (end - start) / 2;:获得中间游标,用减法确保类型范围

每次循环,通过比较更新查找的范围:[start,end]——start = mid + 1; 或 end = mid - 1;

start <= end:两个游标相遇则结束循环

4. 优点、缺点

  • 优点:查找次数MAX:数据(数组)长度/ 2(整除)、折半查找的时间复杂度为O(logn),远远好于顺序查找的O(n)
  • 缺点:虽然二分查找的效率高,但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间

5. 例题

两道来自 leetcode 的题

1、搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素

class Solution {
    public int searchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        int mid = 0;
        while(start <= end) {
            mid = start + (end - start) / 2;// 防止计算时溢出
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[mid] > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
}

查找过程和上面代码一样

return start;:没法查找到存在的返回值。这个值就是目标值理应按顺序插入的位置(从0开始数)

2、第一个错误的版本

由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数

输入:n = 5, bad = 4
输出:4
解释:
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。

错了之后的版本是可以判对的

减少判断次数(调用API )那么根据判错实现对连续的版本号划分区域,从而使用二分法求解

第一个错的版本,他的前面一个版本是被API判错的,例如:输入5,5这样的数据,可以先直接调用API传入4得到false值

再看调用举例,3,5,4:从而推导出每次调用API时传值的计算式

根据调用返回的结果,划分版本号的调查区域。True则为左边的版本号可能出现第一个错误,故start更改;false则为右边的版本号可能出现第一个错误,故n更改

当start、n两个游标相遇,结束循环

返回start的值

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if(!isBadVersion(n - 1)) {
            return n;
        }
        int start = 0;
        while(start <= n) {
            int mid = start + (n - start + 1) / 2;// 防止计算时溢出
            if(isBadVersion(mid)) {
                n = mid - 1;
            } else
                start = mid + 1;
        }
        return start;
    }
}
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        // if(!isBadVersion(n - 1)) {
        //     return n;
        // }
        int start = 1;
        while(start < n) {
            int mid = start + (n - start) / 2;// 防止计算时溢出
            if(isBadVersion(mid)) {
                n = mid;
            } else
                start = mid + 1;
        }
        return start;
    }
}

这个版本才为妥善。start从0开始是一种错误的写法,某种极为特殊的情况下会错误

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容