【查找】- 二分查找

懒猫老师-二分查找基础知识
代码随想录-二分查找基础知识

1 完全有序

1.1 二分查找

二分查找-力扣题目链接

1.1.1 二分查找 （左闭右闭区间）

1.循环退出条件
注意是 low<=high，而不是 low 2.mid 的取值
实际上，mid=(low+high)/2 这种写法是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。
改进的方法是将 mid 的计算方式写成 low+(high-low)/2。
更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 *** 作转化成位运算 low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。
low+(high-low)>>1 是错的，因为 >> 运算的优先级 比 + 运算的优先级低

3.low 和 high 的更新
low=mid+1，high=mid-1。
注意这里的 +1 和 -1，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。
比如，当 high=3，low=3 时，如果 a[3] 不等于 value，就会导致一直循环不退出。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left_index = 0;
        // 定义target在左闭右闭的区间里，[left, right]
        int right_index = nums.size() - 1;
        // 当left==right，区间[left, right]依然有效，所以用 <=
        while(left_index <= right_index)
        {
            int middle_index = left_index + ((right_index - left_index) >> 1);
            if(nums[middle_index] > target)// target 在左区间，所以[left, middle - 1]
                right_index = middle_index - 1;
            else if(nums[middle_index] < target)// target 在右区间，所以[middle + 1, right]
                left_index = middle_index + 1;
            else// nums[middle] == target 数组中找到目标值，直接返回下标
                return middle_index;
        }
        // 未找到目标值
        return -1;
    }
};

1.1.2 递归

509. 斐波那契数

class Solution {
public:
    //1.递归的定义 入参 出参
    int fib(int n) {
        //3.递归的出口
        if(n <= 2)
            return n - 1;
        //2.递归的拆解
        return fib(n - 1) + fib(n - 2);
    }
};

递归实现二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left_index = 0;
        int right_index = nums.size() - 1;
        return binSearch(nums, left_index, right_index, target);
    }
private:
    int binSearch(vector<int>&nums, int left_index, int right_index, int target)
    {
        if (left_index > right_index)
		    return -1;
        int middle_index = left_index + ((right_index - left_index) >> 1);
        if(nums[middle_index] == target)
            return middle_index;
        else if(nums[middle_index] < target)
            return binSearch(nums, middle_index + 1, right_index, target);
        else
            return binSearch(nums, left_index, middle_index - 1, target);               
    }
};

1.2 查找第一/最后一个元素 的位置

在排序数组中查找元素的第一个和最后一个位置-力扣题目链接

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int first_index = searchFirstIndex(nums, target);
        int last_index = searchLastIndex(nums, target);
        return {first_index, last_index};
    }

private:
    int searchFirstIndex(vector<int>& nums, int target)
    {
        int left_index = 0;
        int right_index = nums.size() - 1;
        while(left_index <= right_index)
        {
            int middle_index = left_index +((right_index - left_index) >> 1);
            if(nums[middle_index] > target)
                right_index = middle_index - 1;
            else if(nums[middle_index] < target)
                left_index = middle_index + 1;
            else /*if(nums[middle_index] == target)*/
            {
                //包含两种情况
                //① 0 == middle_index 说明找到的索引就是第一次出现的位置
                //② nums[middle_index - 1] != target 找到的索引的前一个元素不是目标值
                //                               说明找到的索引就是第一次出现的位置
                if(0 == middle_index || nums[middle_index - 1] != target)
                    return middle_index;
                //nums[middle_index - 1] == target 说明找到的索引不是第一次出现的位置
                // 第一次出现的位置应该在[left_index, middle_index - 1]之间
                else
                    right_index = middle_index - 1;
            }
        }
        return -1;
    }

    int searchLastIndex(vector<int>& nums, int target)
    {
        int left_index = 0;
        int right_index = nums.size() - 1;
        while(left_index <= right_index)
        {
            int middle_index = left_index +((right_index - left_index) >> 1);
            if(nums[middle_index] > target)
                right_index = middle_index - 1;
            else if(nums[middle_index] < target)
                left_index = middle_index + 1;
            else /*if(nums[middle_index] == target)*/
            {
                //包含两种情况
                //①(nums.size() - 1) == middle_index 说明找到的索引就是最后出现的位置
                //②nums[middle_index + 1] != target  找到的索引的后一个元素不是目标值
                //                               说明找到的索引就是最后一次出现的位置
                if((nums.size() - 1) == middle_index || nums[middle_index + 1] != target)
                    return middle_index;
                //nums[middle_index + 1] == target 说明找到的索引不是最后一次出现的位置
                //最后一次出现的位置应该在[middle_index + 1, right_index]之间
                else
                    left_index = middle_index + 1;
            }
        }
        return -1;
    }
};

1.3 查找第一个大于等于目标元素的位置

搜索插入位置-力扣题目链接

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
using namespace std;


int searchPosition(vector<int> nums, int target)
{
	int left_index = 0;
	int right_index = nums.size() - 1;
	while (left_index <= right_index)
	{
		int middle_index = left_index + ((right_index - left_index) >> 1);
		if (nums[middle_index] < target)
			left_index = middle_index + 1;
		else //nums[middle_index] >= target
		{
			//两种情况：
			//①0 == middle_index 说明middle_index指向的元素已经是第一个大于等于目标元素的位置
			if (0 == middle_index ||
				//② nums[middle_index - 1] < target middle_index前一个元素的值比目标值小
				//说明middle_index指向的元素已经是第一个大于等于目标元素的位置
				nums[middle_index - 1] < target
				)
			{
				return middle_index;
			}
			else //nums[middle_index - 1] >= target middle_index前一个元素的值 大于等于 目标值
				//							应将范围调整至[left_index, middle_index - 1]之间
			{
				right_index = middle_index - 1;
			}
		}
	}
	//全都比目标值小
	return -1;
}


int main(int argc, char* argv[])
{
	vector<int> nums = { -1, 2, 2, 5, 5, 8 };
	int target = 5;
	int result = searchPosition(nums, target);
	std::cout << "第一个大于等于" << target << "的元素的位置为：" << result << std::endl;
	
	system("pause");
	return 0;
}

1.4 查找最后一个小于等于目标元素的位置

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
using namespace std;


int searchPosition(vector<int> nums, int target)
{
	int left_index = 0;
	int right_index = nums.size() - 1;
	while (left_index <= right_index)
	{
		int middle_index = left_index + ((right_index - left_index) >> 1);
		if (nums[middle_index] > target)
		{
			right_index = middle_index - 1;			
		}		
		else//nums[middle_index] <= target
		{
			//两种情况：
			//①(nums.size() - 1) == middle_index 说明找到的索引已经是最后一个位置
			if ((nums.size() - 1) == middle_index ||
			//②nums[middle_index + 1] > target   找到位置的下一个位置的元素 > target
			//									说明找到的索引已经是最后一个位置
				nums[middle_index + 1] > target)
				return middle_index;
			else//②nums[middle_index + 1] ≤ target   middle_index后一个元素的值 小于等于 目标值
			//应将范围调整至[middle_index + 1, right_index]之间
				left_index = middle_index + 1;
		}
	}
	return -1;
}


int main(int argc, char* argv[])
{
	vector<int> nums = { -1, 2, 2, 5, 5, 8 };
	int target = 2;
	int result = searchPosition(nums, target);
	std::cout << "最后一个小于等于" << target << "的元素的位置为：" << result << std::endl;
	
	system("pause");
	return 0;
}

1.5 找到 K 个最接近的元素

找到 K 个最接近的元素



归并排序

代码解析①：
1.先找到中界线（最后一个小于等于目标元素的位置索引 作为中界线）
2.从中界线两边找到最接近的K 个元素
3.排序

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        //2.2将符合条件的数据存入新的数组
        int left_index = findNearestSmallerIndex(arr, x);
        int right_index = left_index + 1;
        vector<int> nums;
        while(k-- > 0)
        {
            //如果左边更接近，选左边
            if(isLeftNearest(arr, x, left_index, right_index))
            {
                nums.push_back(arr[left_index]);
                left_index--;
            }
            else
            {
                nums.push_back(arr[right_index]);
                right_index++;
            }
        }
        //3.排序
        sort(nums.begin(), nums.end());
        return nums;
    }
private:
    //第一步：先找中界线 （最后一个小于等于目标值的索引）
    int findNearestSmallerIndex(vector<int>& nums, int target)
    {
        if(0 == nums.size())
            return -1;
        int left_index = 0;
        int right_index = nums.size() - 1;
        while(left_index <= right_index)
        {
            int middle_index = left_index +((right_index - left_index) >> 1);
            if(nums[middle_index] > target)
                right_index = middle_index - 1;
            else//nums[middle_index] <= target
            {
                if((nums.size() - 1) == middle_index || nums[middle_index + 1] > target)
                    return middle_index;
                else//nums[middle_index + 1] <= target
                    left_index = middle_index + 1;
            }
        }
        return -1;//所有的数都比目标值大
    }
    //第二步：从中界线两边找到最接近的K 个元素
    //2.1 判断左边元素的最接近目标值
    bool isLeftNearest(vector<int>& nums, int target, int left_index, int right_index)
    {
        //如果左边已经耗尽，没有元素了，肯定右边的最接近，返回false
        if(left_index < 0)
            return false;
        //如果右边已经耗尽，没有元素了，肯定左边的最接近，返回true
        if(right_index >= nums.size())
            return true;
        //为什么有等号？如果左右两边距离相等，选左边
        return target - nums[left_index] <= nums[right_index] - target;
    }
};

代码解析②：
1.先找到中界线（第一个大于等于目标元素的位置索引 作为中界线）
2.从中界线两边找到最接近的K 个元素
3.排序

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        //第一步：找到中界线 right_index 从中界限位置开始
        int right_index = findNearestBiggerIndex(arr, x);//注意：先确定right_index
        int left_index = right_index - 1;
        vector<int> nums;
        //2.2将找到的最接近的k个元素存到一个新的数组中
        while(k-- > 0)
        {
            if(isLeftCloserTarget(arr, x, left_index, right_index))
            {
                nums.push_back(arr[left_index]);
                left_index--;
            }
            else
            {
                nums.push_back(arr[right_index]);
                right_index++;
            }
        }
        //3.排序
        sort(nums.begin(), nums.end());
        return nums;
    }
private:
    //第一步：找到中界线（第一个大于等于目标值的元素）
    //返回的是右边的第一个索引
    int findNearestBiggerIndex(vector<int> arr, int target)
    {
        int left_index = 0;
        int right_index = arr.size();
        while(left_index < right_index)
        {
            int middle_index = left_index +((right_index - left_index) >> 1);
            if(arr[middle_index] < target)
                left_index = middle_index + 1;
            else
            {
                if(0 == middle_index || arr[middle_index - 1] < target)
                    return middle_index;
                else
                    right_index = middle_index;
            }
        }
        return right_index - 1;//所有的元素都比目标值小
    }
    //第二步：找到最接近目标值的k个元素
    //2.1判断左边的元素最接近目标值
    bool isLeftCloserTarget(vector<int> arr, int target, int left_index, int right_index)
    {
        //如果左边的已经耗尽了，那不用比较了，肯定是右边的更接近，返回false
        if(left_index < 0)
            return false;
        //如果右边的已经耗尽了，那不用比较了，肯定是左边的更接近，返回false
        if(right_index >= arr.size())
            return true;
        return (target - arr[left_index]) <= (arr[right_index] - target);
    }
};

2 不完全有序 2.1 查找最大值

852. 山脉数组的峰顶索引
找山顶最大值

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        //特殊情况处理，特殊情况返回值需要跟面试官确认
        if(0 == arr.size())
            return -1;
        //找到第一个符合条件的arr[i] > arr[i + 1]的i
        int left_index = 0;
        int right_index = arr.size() - 1;
        while(left_index <= right_index)
        {
            int middle_index = left_index +((right_index - left_index) >> 1);
            //如果从middle_index 点向右 递减，则山峰一定在middle_index左边，丢掉右边
            if(arr[middle_index] > arr[middle_index + 1])
            {
                right_index = middle_index - 1;
            }
            //如果从middle_index 点向右 递增，则山峰一定在middle_index右边，丢掉左边
            else//arr[middle_index + 1] > arr[middle_index]
            {
                left_index = middle_index + 1;
            }
        }
        //返回left_index 和 right_index 中较大的值的索引，则为山顶
        return arr[left_index] > arr[right_index] ? left_index : right_index;
    }
};

2.2 寻找最小值

153. 寻找旋转排序数组中的最小值

思路

左图 无重复元素 、 排序数组（B部分的数据肯定大于A部分的数据）
经过旋转后 如右图所示（B部分的数据还是大于A部分的数据）
切入点：中界限索引所在的值和数组最后一个元素的值的大小进行比较
① 若 nums[middle_index] > nums.back() —> middle_index 在B部分 —> 最小值应该在右边区间 [middle_index + 1, right_index]之间
②若 nums[middle_index] < nums.back() —> middle_index 在A部分 —> 最小值应该在左边区间 [left_index, middle_index -1]之间

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(0 == nums.size())
            return -1;
        int left_index = 0;
        int right_index = nums.size() - 1;
        while(left_index <= right_index)
        {
            int middle_index = left_index +((right_index - left_index) >> 1);
            if(nums[middle_index] > nums.back())
                left_index = middle_index + 1;
            else
                right_index = middle_index - 1;
        }
        return nums[left_index];
    }
};

2.3 查找目标元素(不包含重复元素)

33. 搜索旋转排序数组


按照这个步骤写的，在测试用例[3, 1] 3的时候没过

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
using namespace std;

//1.找到最小值的索引
int findSmallestIndex(vector<int>& nums)
{
	if (0 == nums.size())
		return -1;
	int left_index = 0;
	int right_index = nums.size() - 1;
	while (left_index <= right_index)
	{
		int middle_index = left_index + ((right_index - left_index) >> 1);
		if (nums[middle_index] > nums.back())
			left_index = middle_index + 1;
		else
			right_index = middle_index - 1;
	}
	return left_index;
}
//二分查找
int binarySearchIndex(vector<int>& nums, int target, int left_index, int right_index)
{
	while (left_index <= right_index)
	{
		int middle_index = left_index + ((right_index - left_index) >> 1);
		if (nums[middle_index] == target)
			return middle_index;
		else if (nums[middle_index] < target)
			left_index = middle_index + 1;
		else if (nums[middle_index] > target)
			right_index = middle_index - 1;
	}
	return -1;
}

int search(vector<int>& nums, int target)
{
	if (0 == nums.size())
		return -1;
	if (1 == nums.size())
		return target == nums[0] ? 0 : -1;
	//2.跟最小值比较确定区间
	int smallest_index = findSmallestIndex(nums);
	int target_index = -1;
	if (target >= nums[smallest_index] && target_index <= nums.back())
		target_index = binarySearchIndex(nums, target, smallest_index, (nums.size() - 1));
	else
		target_index = binarySearchIndex(nums, target, 0, smallest_index - 1);
	return target_index;
}


int main(int argc, char* argv[])
{
	vector<int> nums = { 3, 1 };
	int target = 3;
	int target_index = -1;
	target_index = search(nums, target);
	std::cout << "目标值的索引为 " << target_index << endl;

	system("pause");
	return 0;
}

一次二分查找

注意点：
1.元素不重复
2.每一次分割之后，肯定是一边是单调递增，一边是先递增再递减区间
步骤：
1.先判断左边是不是递增区间
nums[middle_index] >= nums[left_index] -> 左边为递增区间; 否则右边为递增区间
2.再判断目标值在左边区间还是右边区间

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left_index = 0;
        int right_index = nums.size() - 1;
        while(left_index <= right_index)
        {
            int middle_index = left_index + (right_index - left_index) / 2;
            if(nums[middle_index] == target)
                return middle_index;
            //先看左区间[left_index, middle_index]是否为连续递增区间
            if(nums[middle_index] >= nums[left_index])//左边（B的左半部分）为区间连续递增
            {
                //目标元素在左边区间
                if(nums[left_index] <= target && target < nums[middle_index])
                    right_index = middle_index - 1;
                else//目标元素在右边区间
                    left_index = middle_index + 1;
            }
            else//右边（A的右半部分）区间连续递增
            {
                //目标元素在右边区间
                if(nums[middle_index] < target && target <= nums[right_index])
                    left_index = middle_index + 1;
                else//目标元素在左边区间
                    right_index = middle_index - 1;
            }
        }
        return -1;
    }
};

2.4 查找目标元素(包含重复元素)

搜索旋转排序数组 II

class Solution {
public:
 /**
    nums[mid]与nums[l]比较，有三种情况：
    1.nums[mid] > nums[l],则表明[l,mid]是有序的,判断target是否位于有序区间[l,mid-1]中；否则target位于[mid,r]中
    2.nums[mid] < nums[l]，则表明[mid,r]是有序的,判断target是否位于有序区间[mid+1,r]中；否则target位于[l,mid]中
    3.nums[mid] == nums[l],如果nums[l]!=target，我们可以排序左边界l;
      如果nums[l]==target,那么nums[mid]==target，也可以排除左边界l,所以这种情况下让l++即可
     */
    bool search(vector<int>& nums, int target) {
        int left_index = 0;
        int right_index = nums.size() - 1;
        while(left_index <= right_index)
        {
            int middle_index = left_index + (right_index - left_index) / 2;
            if(nums[middle_index] == target)
                return true;
            //区间[left_index, middle_index]是连续递增的
            if(nums[middle_index] > nums[left_index])
            {
                //目标值在左区间[left_index, middle_index]
                if(nums[left_index] <= target && target < nums[middle_index])
                    right_index = middle_index - 1;
                else
                    left_index = middle_index;
            }
            //区间[middle_index, right_index]是连续递增的
            else if(nums[middle_index] < nums[left_index])//2
            {
                //目标值在右区间[middle_index, right_index]
                if(nums[middle_index] < target && target <= nums[right_index])
                    left_index = middle_index + 1;
                else
                    right_index = middle_index;
            }
            else//3
                left_index++;
        }
        return false;
    }
};

2.5 寻找峰值

162. 寻找峰值

2.6 答案集上二分-木材加工（困难）

183 · 木材加工

3 二维数组(二维矩阵找数问题) 3.1 排序矩阵 查找目标元素

74. 搜索二维矩阵
思路

先将二维数组转换成一位数组（一维有序数组）
关键点在于 二维坐标转换成一维坐标

如何确定一维数组在二维数组中的坐标？
如 索引 9 在二维数组中的坐标为[9 / 6, 9 % 6] = [1, 3]
二维数组中的行号 = 一维数组中的索引 / 列数
二维数组中的列号 = 一维数组中的索引 % 列数

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();//m行
        int n = matrix[0].size();//n列
        int left_index = 0;
        int right_index = m * n - 1;
        while(left_index <= right_index)
        {
            int middle_index = left_index +((right_index - left_index) >> 1);
            //求一维数组中索引为middle_index 在二维数组中的值
            //行 = middle_index / n
            //列 = middle_index % n
            int middle_value = matrix[middle_index / n][middle_index % n];
            if(middle_value == target)
                return true;
            else if(middle_value > target)
                right_index = middle_index - 1;
            else
                left_index = middle_index + 1;
        }
        return false;
    }
};

3.2 排序矩阵找数问题 ||

240. 搜索二维矩阵 II

每一行和每一列分别都是排好序的 且 严格递增
不保证下一行都比上一行大.

3.2.1 二分查找

二分查找要对每一行都进行一次二分查找
时间复杂度为O(m) * O(logn) 提交超出时间限制

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(auto vec_nums : matrix)
        {
            int target_index = binarySearch(vec_nums, target);
            if(target_index >= 0)
                return true;
        }
        return false;
    }
private:
    int binarySearch(vector<int>& nums, int target)
    {
        int left_index = 0;
        int right_index = nums.size() - 1;
        while(left_index <= right_index)
        {
            int middle_index = left_index + ((right_index - left_index) >> 1);
            if(nums[middle_index] == target)
                return middle_index;
            else if(nums[middle_index] > target)
                right_index = middle_index - 1;
            else if(nums[middle_index] < target)
                left_index = middle_index + 1;
        }
        return -1;
    }
};

这样遍历又能通过，时间复杂度不是一样的嘛

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();//m行
        int n = matrix[0].size();//n列
        for(int i = 0; i < m; i++)
        {
            int left_index = 0;
            int right_index = n - 1;
            while(left_index <= right_index)
            {
                int middle_index = left_index + ((right_index - left_index) >> 1);
                if(matrix[i][middle_index] == target)
                    return true;
                else if(matrix[i][middle_index] < target)
                    left_index = middle_index + 1;
                else
                    right_index = middle_index - 1;
            }            
        }
        return false;
    }
};

3.2.2 Z字形查找(纵向搜索/单调性扫描)

思路
(单调性扫描) O(n+m)
给定一个m x n 矩阵 matrix，要求我们在这个矩阵中查找目标值 target 。如样例一所示，target = 5，m x n矩阵 matrix中包含5,因此返回true，下面来讲解单调性扫描的做法。
在m x n矩阵 matrix中我们可以发现一个性质：对于每个子矩阵右上角的数x，x左边的数都小于等于x，x下边的数都大于x，如下图所示：

图示

思路

我们可以从整个矩阵的右上角开始枚举，假设当前枚举的数是 x： 如果 x 等于target，则说明我们找到了目标值，返回true； 如果 x小于target，则 x左边的数一定都小于target，我们可以直接排除当前一整行的数； 如果 x 大于target，则 x 下边的数一定都大于target，我们可以直接排除当前一整列的数； 排除一整行就是让枚举的点的横坐标加一，排除一整列就是让纵坐标减一。 当我们排除完整个矩阵后仍没有找到目标值时，就说明目标值不存在，返回false。 具体过程如下： 1、初始化i = 0, j = matrix[0].size() - 1。 2、如果matrix[i][j] == target，返回true。 3、如果matrix[i][j] < target，i++，排除一行。 4、如果matrix[i][j] > target，j–，排除一列。 5、如果出界了还未找到target，则返回false。 时间复杂度分析： 每一步会排除一行或者一列，矩阵一共有 nn 行，mm 列， 所以最多会进行n+mn+m步。所以时间复杂度是 O(n+m)O(n+m)。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(!matrix.size() && !matrix[0].size())
            return false;
        int i = 0, j = matrix[0].size() - 1;//矩阵右上角
        while(i < matrix.size() && j >= 0)
        {
            if(matrix[i][j] == target)
                return true;
            else if(matrix[i][j] < target)//说明目标值在右下角所在行的下面，排除一行
                i++;
            else if(matrix[i][j] > target)//说明目标值在右下角所在列的左，排除一列
                j--;
        }
        return false;
    }
};

3.3 未排序矩阵 输入集 找最小矩阵(困难)

600 · 包裹黑色像素点的最小矩形

3.4 在答案集二分 - 抄书问题

437 · 书籍复印

参考：
1.代码随想录
2.懒猫老师数据结构与算法
3.极客时间|数据结构与算法
4.九章算法