当前位置：首页 > news >正文

c++ || 二分查找

news 来源：原创 2024/5/18 14:23:51

文章目录

二分查找
无重复数字的升序数组的二分查找
二维数组中查找目标整数
寻找峰值
旋转数组中的最小值
搜索插入位置

二分查找

二分查找需要的条件
1.用于查找的内容逻辑上来讲是需要有序的
2.查找的数量只能是一个，不是多个
二分法中关注的问题
1.while循环中left和right的关系，到底是left<=right还是left<right
2.迭代过程中mid和right的关系，到底是right=mid-1，还是right= mid；

对于[left,right]（左闭右闭区间）
循环条件要使用while(left <= right)，因为当(left == right)这种情况发生的时候，得到的结果是有意义的
if(nums[middle] > target) ， right 要赋值为 middle - 1，因为当前的 nums[middle] 一定不是 target ，需要把这个 middle 位置上面的数字丢弃，那么接下来需要查找范围就是[left, middle - 1]

对于[left,right)（左闭右开区间）
循环条件使用while (left < right)
if (nums[middle] > target)， right = middle，因为当前的 nums[middle] 是大于 target 的，不符合条件,不能取到 middle，并且区间的定义是 [left, right)，刚好区间上的定义就取不到 right, 所以 right 赋值为 middle。

无重复数字的升序数组的二分查找

问题：在一个元素升序的，无重复数字的整型数组nums和目标值target，目标值存在返回下标，不存在返回-1
分析：数组为空返回-1；用中点值作为一个标杆，将整个数组分为两个区间，目标值与中点值比较就能知道它会在哪个区间，这就是分治的思维
步骤：
step 1：从数组首尾开始，每次取中点值。
step 2：如果中间值等于目标即找到了，可返回下标，如果中点值大于目标，则中间值向右的所有数字都大于目标值，全部排除。如果中点值小于目标值，则说明中间数字向左的所有数字都小于目标值，全部排除。
step 3：根据比较进入对应的区间，直到区间左右端相遇，意味着没有找到。

    int search(vector<int>& nums, int target) {
        // write code here
        if(nums.empty()) return -1; //为空 -1
        int left=0; //左闭
        int right = nums.size()-1; //右闭
        while(left <= right)   //<=
        {
             int mid = (left+right)/2;
            if(nums[mid]==target)
            {
                return mid;
            }
            if(target < nums[mid])
             right=mid-1; //mid-1
            else left=mid + 1;
        }
        return -1;
    }

      int search(vector<int>& nums, int target) {
        // write code here
        if(nums.empty()) return -1; //为空 -1
        int left=0;   //左闭
        int right = nums.size(); //右开
        while(left < right) //<
        {
             int mid = (left+right)/2;
            if(nums[mid]==target)
            {
                return mid;
            }
            if(target < nums[mid]) right=mid;//mid
            else left=mid + 1;
        }
        return -1;
    }

二维数组中查找目标整数

问题： 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，判断该二维数组中是否有该整数目标，存在返回TRUE，否则返回false；
方法1： 逐行逐个查找

   bool Find(int target, vector<vector<int> > array) {
       for(auto i : array)//c++11语法
        {
            for(auto j : i)
            {
                if(j == target) return true;//找到目标值
            }
        }
        return false;//未找到

方法2： 数组每行每列都是递增的，逐行使用二分搜索，查找target

    bool binary_search(vector<int> & nums,int target)
    {
        int left = 0;
        int right = nums.size()-1;
        while(left<=right)
        {
            int mid = (left+right)/2;
            if(nums[mid]==target) return true;
            if(nums[mid]>target) right=mid-1;
            else left=mid+1;
        }
        return false;
    }
    bool Find(int target, vector<vector<int> > array) {
        if(array.empty()) return false;
        for(auto i:array)
        {
            if(binary_search(i,target)) return true;
        }
        return false;
    }

寻找峰值

问题： 给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = -\infty−∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
分析： 每次找到一个基准元素，将数组分成两个区间，每次都想较高的一边走，就一定能找到一个峰值
步骤： step 1：二分查找首先从数组首尾开始，每次取中间值，直到首尾相遇。
step 2：如果中间值的元素大于它右边的元素，说明往右是向下，我们不一定会遇到波峰，但是那就往左收缩区间。
step 3：如果中间值大于右边的元素，说明此时往右是向上，向上一定能有波峰，那我们往右收缩区间。
step 4：最后区间收尾相遇的点一定就是波峰。

    int findPeakElement(vector<int>& nums) {
        // write code here
        int left = 0;
        int right = nums.size() - 1;
        //二分法
        while(left < right){
            int mid = (left + right) / 2;
            //右边是往下，不一定有坡峰
            if(nums[mid] > nums[mid + 1])
                right = mid;
            //右边是往上，一定能找到波峰
            else
                left = mid + 1;
        }
        //其中一个波峰
        return right;
    }

旋转数组中的最小值

**问题： ** 旋转数组的最小数字：把一个数组最开始的若干个元素搬到数组的末尾，称为数组的旋转
{3,4,5,1,2} -> {1,2,3,4,5}
思路：二分查找法 O(logn)
注:旋转数组中包含两个递增排序的子数组，有阴影的是第二个子数组。
(a)把P1指向数组的第一个数字，Pz指向数组的最后一个数字。
由于P1和P2中间的数字5 [(first+last)/2] 大于P1指向的数字，中间的数字在第一个子数组中，下一步把P1指向中间的数字。
(b)P1和P2中间的数字1,小于P2指向的数字，中间的数字在第二个子数组中。下一步把P2指向中间的数字。
©退出的条件：P1和P2指向两个相邻的数字(两个指针的距离是1)，则P2指向的是数组中的最小数字。

特殊情况：当first、last、index指向的数字相同时，无法判断中间的数字是在第一个子数组还是在第二个子数组中，
也就没有办法移动指针缩小查找的范围，只能使用顺序查找


int MinSort(int* arr, int first, int last) //按顺序从前到后逐个遍历找出最小值
{
	int res = arr[first];
	for (int i = first + 1; i < last; ++i)
	{
		if (res > arr[i]) res = arr[i];
	}
	return res;
}
int Min(int* arr, int length)     //二分查找最小值
{
	if (arr == nullptr || length <= 0)return -1;
	int first = 0;
	int last = length - 1;
	int index = first;
	while (arr[first] >= arr[last])
	{
		if (last - first == 1)//循环退出的条件是 last和first之间距离为1
		{//此时first指向的是第一个数组的最后一个元素
			//last指向的是第二个数组的第一个元素
			index = last;
			break;
		}
		index = (first + last) / 2;
		if (arr[first] == arr[last] && arr[first] == arr[index])
		{ //下标为first、last、index指向的数字都相等 则只能顺序查找
			return MinSort(arr, first, last);
		}
		if (arr[index] >= arr[first])
		{
			first = index;
		}
		else if (arr[index] <= arr[last])
		{
			last = index;
		}
	}
	return arr[index];
}
int main()
{
	//int a[] = { 3,4,5,1,2 };
	int a[] = { 1,0,1,1,1 };
	int n = sizeof(a) / sizeof(a[0]);
	int min = Min(a, n);
	cout << "旋转数组中最小的数字是：" << min << endl;
	return 0;
}

搜索插入位置

问题： 给定排序数组和目标值，在数组中找到目标值，返回其索引，目标值不存在与数组中，返回他将会被按顺序插入的位置
分析： 四种情况
1.目标值在数组所有元素之前 [0，-1]
2.目标值等于数组中某一元素 return mid；
3.目标值插入数组中的位置 [left,right] returnright+1
4.目标值在数组所有元素之后 [left,right] return right+1

    int searchInsert(vector<int>& num, int target) {
        int n=num.size();
        int left=0;
        int right=n-1;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(num[mid]>target)
            {
                right=mid-1;
            }
            else if(num[mid]<target )
            {
                left=mid+1;
            }
            else{
                return mid;
            }
        }
        return right+1;
    }