算法——二分查找相关题目
- 题目：
-
- leetcode 704.二分查找
- leetcode 35.搜索插入位置
- leetcode 34.在排序数组中查找元素的第一个和最后一个位置
- leetcode 69.Sqrt(x)
- leetcode 367.有效的完全平方数
- leetcode 744.寻找比目标字母大的最小字母
- leetcode 852.山脉数组的峰顶索引
- leetcode 74.搜索二维矩阵
- leetcode 540.有序数组中的单一元素
- leetcode 875.爱吃香蕉的珂珂
- leetcode1011.在 D 天内送达包裹的能力
- leetcode 1292.元素和小于等于阈值的正方形的最大边长
- leetcode 354.俄罗斯套娃信封问题
- leetcode 410.分割数组的最大值（困难：用二分查找优化算法效率）
题目：
leetcode 704.二分查找
leetcode 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
思路
考虑数组中插入目标值的四种情况：
- 目标值在数组所有元素之前
- 目标值等于数组中某一个元素
- 目标值插入数组中的位置
- 目标值在数组所有元素之后
1.暴力解法
时间复杂度：O(n)
class Solution {
public int searchInsert(int[] nums, int target) {
for (int i=0;i<nums.length;i++) {
if (nums[i]>=target) {
return i;
}
}
return nums.length;
}
}
2.二分法
时间复杂度：O(logn)
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left<=right) {
int mid = left + (right-left)/2;
if (nums[mid]<target) {
left = mid + 1;
} else if (nums[mid]>target) {
right = mid - 1;
} else {
return mid;
}
}
// 目标值在数组所有元素之前 [0, -1]
// 目标值等于数组中某一个元素 return middle;
// 目标值插入数组中的位置 [left, right]，return right + 1
// 目标值在数组所有元素之后的情况 [left, right]， return right + 1
return right + 1;
}
}
中等
leetcode 34.在排序数组中查找元素的第一个和最后一个位置
leetcode 34.在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：你可以设计并实现时间复杂度为 O ( log n ) O(\log n) O(logn) 的算法解决此问题吗？
示例 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]
思路
寻找target在数组里的左右边界，有三种情况：
情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}；数组{3,6,6,7},target为6，此时应该返回{1, 2}
二分法查找边界解决
class Solution {
public int[] searchRange(int[] nums, int target) {
int leftbord = LeftBord(nums,target);
int rightbord = RightBord(nums,target);
if (leftbord == -2 || rightbord == -2) {
return new int[] {-1,-1}; //情况1
}
if (rightbord - leftbord > 1) { //情况3
return new int[] {leftbord+1,rightbord-1}; //返回的leftbord,rightbord是第一个不等于target的索引，所以要+1、-1后输出
}
return new int[] {-1,-1}; //情况2
}
int LeftBord(int[] nums,int target) { //左边界
int left = 0;
int right = nums.length - 1;
int leftbord = -2; //初值，记录未赋值的情况
while (left<=right) {
int mid = left + (right-left)/2;
if (nums[mid]<target) {
left = mid + 1;
} else {
right = mid -1;
leftbord = right;
}
}
return leftbord;
}
int RightBord(int[] nums,int target) { //右边界
int left = 0;
int right = nums.length - 1;
int rightbord = -2; //初值，记录未赋值的情况
while (left<=right) {
int mid = left + (right-left)/2;
if (nums[mid]>target) {
right = mid - 1;
} else {
left = mid + 1;
rightbord = left;
}
}
return rightbord;
}
}
leetcode 69.Sqrt(x)
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
思路
1.二分查找
x 平方根的整数部分ans 是满足 k^2 ≤ x 的最大 k 值，因此我们可以对 k 进行二分查找，查找区间为[0,x)；f(k)=k2，k为整数时单调递增；找满足k2 ≤ x 的最大k值。
时间复杂度：O(logx)
class Solution {
public int mySqrt(int x) {
int left = 0, right = x;
int ans = -1;
while (left<=right) {
int mid = left + (right - left)/2;
if ((long)mid*mid <= x) { //注意防止mid*mid越界
ans = mid; //记录符合的mid值
left = mid + 1;
} else {
right = mid -1;
}
}
return ans;
}
}
2.牛顿迭代法
牛顿迭代法是一种可以用来快速求解函数零点的方法。
为了叙述方便，我们用 a 表示待求出平方根的那个整数。显然，a 的平方根就是函数
y = f(x) = x^2 - a
的零点。
牛顿迭代法的本质是借助泰勒级数，从初始值开始快速向零点逼近。我们任取一个x0作为初始值，在每一步的迭代中，找到函数图像上的点 (xi ,f(xi ))，过该点作一条斜率为该点导数 f ′ (xi ) = 2xi 的直线（切线），与横轴的交点记为 xi+1。
x i+1相较于xi而言距离零点更近。在经过多次迭代后，我们就可以得到一个距离零点非常接近的交点。
x−f(x)/(2x) 就是一个比 x 更接近的近似值。代入 f(x)=x^2 −a 得到 x-(x^2-a)/(2x)，也就是 (x+a/x)/2。
时间复杂度：O(logx)（此方法是二次收敛的，相较于二分查找更快）
class Solution {
public int mySqrt(int x) { //这里的a、x与上面相反
long a = x;
while (a * a > x) {
a = (a + x / a) / 2;
}
return (int)a;
}
}
leetcode 367.有效的完全平方数
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false
思路
与上一题Sqrt(x)很像，更容易，直接二分查找确定值即可。
也可使用牛顿迭代
class Solution {
public boolean isPerfectSquare(int num) {
int left=0,right=num;
while (left<=right) {
int mid = left+(right-left)/2;
if ((long)mid*mid>num) {
right = mid - 1;
} else if ((long)mid*mid<num) {
left = mid + 1;
} else {
return true;
}
}
return false;
}
}
leetcode 744.寻找比目标字母大的最小字母
给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时，字母是依序循环出现的。举个例子：
如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’
思路
找有序列表里比目标字母大的最小字母，实际上就是找右侧边界，保证该边界值 > 目标值。
注意：如果查找到对应的位置是最后一个位置 letters.length，则返回 letters[0]。通过模运算的运用可以保证这一点。
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int left=0,right=letters.length-1;
while (left<=right) {
int mid = left + (right-left)/2;
if (letters[mid]>target) {
right = mid - 1;
} else if (letters[mid]<=target) {
left = mid + 1;
}
}
//如果对应位置是最后的位置letters.length，则返回letters[0]
return letters[left % letters.length];
}
}
leetcode 852.山脉数组的峰顶索引
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right-left)/2;
if (mid-1>=0 && arr[mid]<=arr[mid-1])
right = mid - 1;
else if (mid+1<=arr.length-1 && arr[mid]<=arr[mid+1])
left = mid + 1;
else
return mid;
}
return -1; //确定是山脉数组，其实不会返回-1
}
}
leetcode 74.搜索二维矩阵
一次大二分查找：
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int first = 0;
int last = m*n-1;
while (first <= last) {
int mid = first + (last-first)/2;
if (matrix[mid/n][mid%n]>target)
last = mid - 1;
else if (matrix[mid/n][mid%n]<target)
first = mid + 1;
else
return true;
}
return false;
}
}
也可以对行列进行两次二分查找
leetcode 540.有序数组中的单一元素
leetcode 875.爱吃香蕉的珂珂
leetcode1011.在 D 天内送达包裹的能力
leetcode 1292.元素和小于等于阈值的正方形的最大边长
leetcode 1292.元素和小于等于阈值的正方形的最大边长
leetcode 354.俄罗斯套娃信封问题
leetcode 410.分割数组的最大值（困难：用二分查找优化算法效率）
1062、1231