lc 69. Sqrt(x) 28:30
lc 35. Search Insert Position 41:36
lc 34. Find First and Last Position of Element in Sorted Array 50:43
lc 74. Search a 2D Matrix 59:48
lc 153. Find Minimum in Rotated Sorted Array 71:35
lc 33. Search in Rotated Sorted Array 86:02
lc 278. First Bad Version 102:17
lc 162. Find Peak Element 106:39
lc 287. Find the Duplicate Number 119:06
lc 275. H-Index II 129:47
https://www.bilibili.com/video/BV1Ft41157zW
二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。
版本1
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。
C++ 代码模板：
int bsearch_1(int l, int r){while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;}
版本2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。
C++ 代码模板：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
69. x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。
class Solution {
public int mySqrt(int x) {
int l = 0, r = x;
while (l < r) {
int mid = l + r + 1 >> 1;
if (mid <= x/mid) l = mid ;
//check为t方<=x,满足的根号x取下整是左边的最后一个，用模板二，
//如果mid满足，则根号x要在mid右边，那么l=mid，不满足则，r=mid-1
else
r = mid -1;
}
return r;
}
}
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
class Solution {
public int searchInsert(int[] nums, int target) {
if(nums.length==0||nums[nums.length-1]<target)//特别判断
return nums.length;
int l=0,r=nums.length-1;
while(l<r){
int mid =l+r>>1;
if(nums[mid]>=target) r=mid;
//确定check为t>=targrt,那么就是右边合法的第一个，就用模板一
else
l=mid+1;
}
return l;
}
}
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
- 你可以设计并实现时间复杂度为
O(log n)的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length==0)
return new int[]{-1, -1};//判断为空
int l=0,r=nums.length-1;
while(l<r){
int mid =l+r>>1;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}//找出大于等于target的起始位置，对应模板一
if(nums[r]!=target)
return new int[]{-1, -1};
r=nums.length-1;
int start =l;//从剩下的部分找出小于等于（小于）target的结束位置，对应模板二
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid]<=target) l = mid ;
else
r = mid -1;
}
int end =r;
return new int[]{start, end};
}
}
74. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m=matrix.length,n=matrix[0].length;//二维数组性质，m为行数，n为列数m*n为长度
int l=0,r=m*n-1;
while(l<r){
int mid =l+r>>1;
if(matrix[mid/n][mid%n]>=target) r=mid;//求出相应位置的值matrix[mid/n][mid%n],因为从0开始，所以mid%n不需要减1
else l=mid+1;
}
if(matrix[r/n][(r%n)]==target)
return true;
else
return false;
}
}
//下面提供线性扫描的方法，先扫描第一列，找出所在行，然后再判断是否存在
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m=matrix.length,n=matrix[0].length;
int res=0;//存储最终结果
for(int i=n-1;i<m*n;i=i+n){//遍历数组的每一行的最后一个元素
if(matrix[i/n][i%n]>=target&&matrix[i/n][0]<=target){//看这一行的第一个和最后一个是否满足
int l=i-n+1,r=i;
while(l<r){
int mid =l+r>>1;
if(matrix[mid/n][mid%n]>=target) r=mid;//利用二分，模板1找出大于等于的第一个元素
else l=mid+1;
}
res=l;
}
}
if(matrix[res/n][(res%n)]==target)
return true;
else
return false;
}
}
153. 寻找旋转排序数组中的最小值
假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。
请找出其中最小的元素。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
示例 3：
输入：nums = [1]
输出：1
class Solution {
public int findMin(int[] nums) {
int l=0,r=nums.length-1;
while(l<r){
int mid=l+r>>1;
if(nums[mid]<=nums[nums.length-1]) r=mid;//利用最后一个元素的关系划分整个数组
else l=mid+1;
}
return nums[l];
}
}
33. 搜索旋转排序数组
难度中等1150收藏分享切换为英文接收动态反馈
升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
class Solution {
public int search(int[] nums, int target) {
int l=0,r=nums.length-1;
while(l<r){
int mid=l+r>>1;
if(nums[mid]<=nums[nums.length-1]) r=mid;//利用最后一个元素的关系划分整个数组
else l=mid+1;
}
if(target<=nums[nums.length-1])//增加判断属于哪一段，进行区间选择
r=nums.length-1;
else{
r--;
l=0;
}
while(l<r){
int mid=l+r>>1;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
if(target==nums[l])//r可能为-1，所以用l
return l;
else
return -1;
}
}
278. 第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int l=1,r=n;
while(l<r){
int mid=l+(r-l)/2;//对int溢出进行判断
if(isBadVersion(mid)) r=mid;
else l=mid+1;
}
return r;
}
}
162. 寻找峰值
峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
class Solution {
public int findPeakElement(int[] nums) {
int l=0,r=nums.length-1;
while(l<r){
int mid =l+r>>1;
if(nums[mid]>nums[mid+1]) r=mid;//mid+1可能存在边界问题，因为while保证l!=r,所以不存在l=r=n-1
else l=mid+1;
}
return l;
}
}
287. 寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
示例 3：
输入：nums = [1,1]
输出：1
示例 4：
输入：nums = [1,1,2]
输出：1
class Solution {
public int findDuplicate(int[] nums) {
int l=1,r=nums.length-1;
while(l<r){
int mid =l+r>>1;
int cnt=0;
for(int x:nums)//遍历数组看是否
if(x>=l&&x<=mid)
cnt++;
if(cnt>mid-l+1) r=mid;
else l=mid+1;
}
return r;
}
}
class Solution {
public int findDuplicate(int[] nums) {
int[] myList = new int[nums.length];//hash的思想
for(int i=0;i<nums.length;i++){
myList[nums[i]]++;
if(myList[nums[i]]==2)
return nums[i];
}
return 0;
}
}
275. H 指数 II
难度中等82收藏分享切换为英文接收动态反馈
给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照 升序排列 。编写一个方法，计算出研究者的 h 指数。
h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）”
示例:
输入: citations = [0,1,3,5,6]
输出: 3
解释: 给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
由于研究者有 3篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，所以她的 h 指数是 3。
class Solution {
public int hIndex(int[] citations) {
int l=0,r=citations.length;
while(l<r){
int mid=l+r>>1;
if(citations[citations.length-mid]>mid) l=mid;
//至少存在h个数>=h,check为倒数第h大于等于mid
else r=mid-1;
}
return citations[r];
}
}
若有收获，就点个赞吧
0 人点赞
