二分法特性
- 已经排好序
- 时间复杂度 logn
做题重要考虑点
- 初始条件 max=? min=?
- 最后没找到，最后的输出结果应该是min还是max？
由于循环条件（min<=max），若没有找到的话退出循环，此时min>max（min等于max+1），要根据题目要求看要min还是要max。如输出的是查询失败后应该插入的位置：应该是min（右边位置）。但是若是x的平方根（8的话是2.82842向下取整等于2）就是输出max（左边位置）。
35（二分法）搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
class Solution
{
public:
int searchInsert(vector<int>& nums, int target)
{
int min = 0;
int max = nums.size()-1;
int mid = 0;
while(min<=max)
{
mid = (min + max)/2;
if(nums[mid]==target)
{
return mid;
}
else if(target>nums[mid])
{
min = mid+1;
}
else
{
max = mid-1;
}
}
return min;
}
};
- 初始化max = length -1 数组下标等于位置-1
- 新边界
max = mid -1或者min = mid +1- 循环控制：min <=max
- 搜索结束：
- 找到：输出位置mid
- 没找到的话（min>max）：mid = min 是应该插入的位置
69 x的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
- 输入4得2，输入8也得2
class Solution {
public:
int mySqrt(int x) {
int max = x/2;
int min = 1;
int mid = 0;
if(x==0) return 0;
if(x==1) return 1;
while(min<=max)
{
mid = (min+max)/2;
if(mid<x/mid)
{
min = mid+1;
}
else if(mid>x/mid)
{
max = mid-1;
}
else
{
return mid;
}
}
return max;
}
};
- 初始条件 r等于x/2就行，min=1
- 注意最后没找到的话返回的值是max(因为是舍去小数部分)，而此时max是小于min的，取小的值。
- 注意当x==0跟x==1的特殊情况。
167. 两数之和 II - 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
思路:两层循环，第一层：左边固定一个x，第二层：后面用二分查找y,找x+y=target。
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int min;
int max;
int mid;
for(int i=0;i<numbers.size();i++)
{
min = i+1;
max = numbers.size()-1;
while(min<=max)
{
mid = (max-min)/2+min;
if(numbers.at(mid)>target-numbers.at(i))
{
max = mid-1;
}
else if(numbers.at(mid)<target-numbers.at(i))
{
min = mid+1;
}
else
{
return {i+1,mid+1};
}
}
}
return {};
}
};
- 加变减是为了防止整数溢出
- mid = (max-min)/2+min;
- if(numbers.at(mid)>target-numbers.at(i))
- 返回值
- return {1,1}就是返回了一个vector
- return {} 就是返回了一个空vector
33.搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
class Solution {
public:
int search(vector<int>& nums, int target) {
int max = nums.size()-1;
int min=0;
int mid;
while(min <= max)
{
mid = (max - min)/2 + min;
if(nums[mid] == target)
{
return mid;
}
else
{
if(nums[mid]>=nums[min])
{//左边有序
if(target>=nums[min]&&target<nums[mid])
{//target在有序侧
max = mid - 1;
}
else
{//target在有序侧
min = mid + 1;
}
}
else
{//右边有序
if(target<=nums[max]&&target>nums[mid])
{//target在有序侧
min = mid + 1;
}
else
{//target在有序侧
max = mid - 1;
}
}
}
}
return -1;
}
};
- 思路分两步
1. 确定mid左边有序还是右边有序
2. 判断target是否在有序区间位置来判断target是在mid左边还是右边
- 二分法：判断target是在左边还是右边
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int max = nums.size()-1;
int min = 0;
int mid;
int a,b;
while(min <= max)
{
mid = (max - min)/2 + min;
if(target==nums[mid])
{
a = b = mid;
while(a>=0&&nums[a]==target)
{
a--;
}
while(b<=nums.size()-1&&nums[b]==target)
{
b++;
}
return {a+1,b-1};
}
else if(target < nums[mid])
{
max = mid - 1;
}
else
{
min = mid + 1;
}
}
return {-1,-1};
}
};
很简单，按普通二分查找找到位置后，向前向后找边界即可
注意下标不要越界
74. 搜索二维矩阵
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int min=0;
int max=matrix.size()-1;
if(matrix.size()==0 || matrix[0].size()==0) return false; //避免数组越界
while(min<=max)
{
int mid = (max-min)/2+min;
if(matrix[mid][0]==target)
{
return true;
}
else if(matrix[mid][0]<target)
{
min = mid + 1;
}
else
{
max = mid - 1;
}
}
if(max==-1) return false; //避免数组越界
int temp = max;
min = 0;
max = matrix[temp].size()-1;
while(min<=max)
{
int mid = (max-min)/2+min;
if(matrix[temp][mid]==target)
{
return true;
}
else if(matrix[temp][mid]<target)
{
min = mid + 1;
}
else
{
max = mid - 1;
}
}
return false;
}
};
本人方法，较笨，先二分查找，找在哪一个一位数组中，再在此一位数组中二分查找
需要多次考虑边界问题防止数组越界
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
if (m == 0) return false;
int n = matrix[0].size();
// 二分查找
int left = 0, right = m * n - 1;
int pivotIdx, pivotElement;
while (left <= right) {
pivotIdx = (left + right) / 2;
pivotElement = matrix[pivotIdx / n][pivotIdx % n];
if (target == pivotElement) return true;
else {
if (target < pivotElement) right = pivotIdx - 1;
else left = pivotIdx + 1;
}
}
return false;
}
};
leetcode官方题解
核心思想是将二维数组转化为一维数组之后用标准的二分查找解决
