type
status
password
date
slug
summary
category
URL
tags
icon
二分查找基本原理
- 算法流程
- 建模：划分蓝红区域，确定划分条件
IsBlue() - 确定返回 l 还是 r。如右图所示不同条件小的返回值
- 套用算法模板
- 后续处理(返回查找值等)
重点边界条件是
left+1<right，这样再执行一次恰好会使得l、r相邻(left<right)。经典二分查找算法
任务 | 示例 | 根据上述模板的基本思想如下 |
目标值是否存在 | 第一个大于等于目标值的索引，然后判断第一个值是不是目标值
最后一个小于等于目标值的索引，然后判断最后一个是不是目标值 | |
目标值在数组中第一个、最后一个位置 | 第一个大于等于目标值的索引
最后一个小于等于目标值的索引 | |
要插入的位置 | 第一个大于等于目标值的位置 |
查找目标值
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
74. 搜索二维矩阵 - 力扣（LeetCode）
将二维数组变成一维数组[0,…,row*col]，那么一维数组与二维数组的对应关系就是
278. 第一个错误的版本 - 力扣（LeetCode）
你有
n 个版本 [1, 2, ..., n]的软件，你想找出导致之后所有版本出错的第一个错误的版本。35. 搜索插入位置 - 力扣（LeetCode）
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
示例
数值二分型
如果符合有序这一特性的数值二分型题目同样可以使用上述模板。但是数值型不用考虑超出边界的问题。
题目 | 范围 | 特性 | 使用上述模板 |
[1，n] | 单调递增 | 可以 | |
正整数 | 单调递增 | 可以 | |
非负数 | 单调递增 | 可以 |
374. 猜数字大小 - 力扣（LeetCode）
每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
你可以通过调用一个预先定义好的接口int guess(int num)来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
- 1：我选出的数字比你猜的数字小 pick < num
- -1：我选出的数字比你猜的数字大 pick > num
- 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！
pick == num
367. 有效的完全平方数 - 力扣（LeetCode）
给你一个正整数
num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。