首页 > 其他分享 >【hot100】二分查找

【hot100】二分查找

时间：2024-12-04 18:01:06浏览次数：9  
标签：二分 right target nums int mid 查找 hot100 left

文章目录

二分写法

  • 当target存在多个时，需要注意判断条件nums[mid]和target之间用>、
  • <、>=、<=，这决定了是获取target 最左侧的索引，还是最右侧的索引；

获取等于target的最左侧的索引

第一种写法

class Solution {
public:
    int binary_search(vector<int>& nums, int target) {


        int left = 0 ,right = nums.size()-1;

        while(left <= right)
        {
            int mid = left + (right - left)/2;
            
            if(nums[mid] < target)
            {
                left =mid +1 ;
            }
            else
            {
                right = mid - 1;
            }

        }
		return left
    }
};

第二种写法

    int binart_search(vector<int>& nums, int target) {
        int left = -1, right = nums.size(); // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid; // 范围缩小到 (left, mid)
            } else {
                left = mid; // 范围缩小到 (mid, right)
            }
        }
        // 循环结束后 left+1 = right
        // 此时 nums[left] < target 而 nums[right] >= target
        // 所以 right 就是第一个 >= target 的元素下标
        return right;
    }

获取等于target的最右侧的索引

class Solution {
public:
    int binary_search(vector<int>& nums, int target) {


        int left = 0 ,right = nums.size()-1;

		while(left <= right)
        {
            int mid = left + (right - left)/2;
            
            if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else
            {
                left = mid  +1;
            }

        }
		return right
    }
};

35. 搜索插入位置

在这里插入图片描述

二分实现

  • 时间复杂度：O(logn)，其中 n 为 nums 的长度。
  • 空间复杂度：O(1)，仅用到若干额外变量。
  • 这种实现方式，一定要注意， if (nums[mid] < target) 的判断，不能改成 if (nums[mid] > target) , 这里决定了是right向left靠近，还是left 向right 靠近

我的代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 初始化左右指针，left 指向数组的起始位置，right 指向数组的末尾位置
        int left = 0, right = nums.size() - 1;

        // 当 left <= right 时循环，即当搜索区间有效时进行二分查找
        while (left <= right) {
            // 计算中间位置，避免使用 (left + right) / 2 来防止可能的整数溢出
            int mid = left + (right - left) / 2; 

            // 如果中间值小于目标值，则目标值应该在右半部分，更新 left
            if (nums[mid] < target) {
                left = mid + 1;
            } 
            // 如果中间值大于或等于目标值，则目标值应该在左半部分（包括当前位置），更新 right
            else {
                right = mid - 1;
            }
        }

        // 循环结束时，left 是目标值应插入的位置，也是目标值第一次出现的位置（如果存在）
        return left;
    }
};

74. 搜索二维矩阵

在这里插入图片描述
在这里插入图片描述

O(logmn) 解法

  • 时间复杂度：O(log(mn))，其中 m 和 n 分别为 matrix 的行数和列数。
  • 空间复杂度：O(1)
  • 这里我和灵神的处理方法不同
    • 灵神思路：把矩阵视为一个数组，进行索引的映射
    • 我的思路：进行两次二分查找，先查在哪一行，再查在行中的具体位置

灵神思路：更简洁

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 检查矩阵是否为空或第一行是否为空，若为空则直接返回 false
        if (matrix.empty() || matrix[0].empty()) return false;

        // 获取矩阵的行数 n 和列数 m
        int n = matrix.size(), m = matrix[0].size();

        // 初始化左右指针，用于在“拉直”的一维数组中进行二分查找
        int left = 0, right = n * m - 1;

        // 当 left <= right 时循环，即当搜索区间有效时进行二分查找
        while (left <= right) {
            // 计算中间位置，避免使用 (left + right) / 2 来防止可能的整数溢出
            int mid = left + (right - left) / 2;

            // 将一维索引 mid 转换为二维坐标 [mid / m][mid % m]，以访问对应的矩阵元素
            int midValue = matrix[mid / m][mid % m];

            // 如果找到目标值，返回 true
            if (midValue == target) {
                return true;
            }
            // 如果中间值小于目标值，则目标值应该在一维数组的右半部分，更新 left
            else if (midValue < target) {
                left = mid + 1;
            }
            // 如果中间值大于目标值，则目标值应该在一维数组的左半部分，更新 right
            else {
                right = mid - 1;
            }
        }

        // 如果遍历完所有可能的位置后仍未找到目标值，返回 false
        return false;
    }
};

我的代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        int m = matrix[0].size();

        int left = 0, right = n - 1;
        int mid = left + (right - left) / 2;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (matrix[mid][m - 1] < target) {
                left = mid +1;
            } else {
                right = mid - 1;
            }
        }

        int idx = left;

        if (idx == n )
            return false;
        left = 0, right = m - 1;
        while (left <= right) {
            mid = left + (right - left) / 2;
            
            if(matrix[idx][mid] == target) return true;
            else  if(matrix[idx][mid] > target)
            {
                right = mid -1;
            }
            else 
            {
                left = mid +1;
            }
        }

        return false;
    }
};

O（n + logm）解法

时间复杂度：O(n+log(m))，其中 m 和 n 分别为 matrix 的行数和列数。
空间复杂度：O(1)。

我的代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 获取矩阵的行数 n 和列数 m
        int n = matrix.size();
        if (n == 0) return false; // 如果矩阵为空，直接返回 false
        int m = matrix[0].size();

        // 遍历每一行
        for (int i = 0; i < n; i++) {
            // 初始化左右指针，用于在当前行内进行二分查找
            int left = 0, right = m - 1;

            // 如果当前行的第一个元素大于目标值，说明该行及之后的所有行都不可能包含目标值
            if (matrix[i][left] > target)
                return false;
            
            // 如果当前行的最后一个元素小于目标值，跳过该行，继续检查下一行
            if (matrix[i][right] < target)
                continue;

            // 在当前行内执行二分查找
            while (left <= right) {
                // 计算中间位置，避免使用 (left + right) / 2 来防止可能的整数溢出
                int mid = left + (right - left) / 2;

                // 如果找到目标值，返回 true
                if (matrix[i][mid] == target)
                    return true;
                
                // 如果中间值大于目标值，则目标值应该在左半部分，更新 right
                else if (matrix[i][mid] > target) {
                    right = mid - 1;
                } 
                // 如果中间值小于目标值，则目标值应该在右半部分，更新 left
                else {
                    left = mid + 1;
                }
            }
        }

        // 如果遍历完所有行后仍未找到目标值，返回 false
        return false;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

在这里插入图片描述

二分查找

  • 时间复杂度：O(logn)，其中 n 为 nums 的长度。
  • 空间复杂度：O(1)，仅用到若干额外变量。
class Solution {
    // lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    // 如果数组为空，或者所有数都 < target，则返回 nums.size()
    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    int lower_bound(vector<int>& nums, int target) {
        int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right]
        while (left <= right) { // 区间不为空
            // 循环不变量：
            // nums[left-1] < target
            // nums[right+1] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1; // 范围缩小到 [left, mid-1]
            } else {
                left = mid + 1; // 范围缩小到 [mid+1, right]
            }
        }
        // 循环结束后 left = right+1
        // 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
        // 所以 left 就是第一个 >= target 的元素下标
        return left;
    }

public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lower_bound(nums, target);
        if (start == nums.size() || nums[start] != target) {
            return {-1, -1}; // nums 中没有 target
        }
        // 如果 start 存在，那么 end 必定存在
        int end = lower_bound(nums, target + 1) - 1;
        return {start, end};
    }
};

33. 搜索旋转排序数组

在这里插入图片描述

两次二分

  • 时间复杂度：O(logn)，其中 n 为 nums 的长度。
  • 空间复杂度：O(1)，仅用到若干额外变量。

我的代码

class Solution {
    // 辅助函数：执行标准二分查找，返回 target 应该插入的位置或其索引
    int binarySearch(vector<int> &nums, int target, int left, int right) {
        while (left <= right) {
            int mid = left + (right - left) / 2; // 计算中间位置，防止溢出

            if (nums[mid] < target) {
                left = mid + 1; // 如果中间值小于目标值，则目标值应该在右半部分
            } else {
                right = mid - 1; // 如果中间值大于或等于目标值，则目标值应该在左半部分（包括当前位置）
            }
        }

        return left; // 返回目标值应插入的位置或找到的目标值索引
    }

public:
    // 主函数：在一个可能旋转过的排序数组中查找目标值
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return -1; // 如果数组为空，直接返回 -1

        int m = nums[0]; // 获取原始数组的第一个元素，用于判断旋转点
        int left = 0, right = n - 1;

        // 寻找旋转点，即最小元素的位置
        while (left <= right) {
            int mid = left + (right - left) / 2; // 计算中间位置，防止溢出

            if (nums[mid] >= m) {
                left = mid + 1; // 如果中间值大于等于第一个元素，说明旋转点在右侧
            } else if (nums[mid] < m) {
                right = mid - 1; // 如果中间值小于第一个元素，说明旋转点在左侧或就是当前位置
            }
        }

        // 在旋转点两侧分别进行二分查找
        int idx1 = binarySearch(nums, target, 0, right); // 在旋转点左侧查找
        if (idx1 <= right && nums[idx1] == target) return idx1; // 如果找到目标值，返回其索引

        int idx2 = binarySearch(nums, target, left, n - 1); // 在旋转点右侧查找
        if (idx2 >= left && idx2 <= n - 1 && nums[idx2] == target) return idx2; // 如果找到目标值，返回其索引

        return -1; // 如果遍历结束仍未找到目标值，返回 -1
    }
};

一次二分

  • 时间复杂度：O(logn)，其中 n 为 nums 的长度。
  • 空间复杂度：O(1)，仅用到若干额外变量。

我的代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 如果找到了目标值，直接返回其索引
            if (nums[mid] == target) return mid;

            // 判断哪边是有序的，并根据有序的部分调整搜索范围
            if (nums[left] <= nums[mid]) { // 左半部分有序
                if (nums[left] <= target && target < nums[mid]) {
                    // 目标值在左半部分
                    right = mid - 1;
                } else {
                    // 目标值在右半部分
                    left = mid + 1;
                }
            } else { // 右半部分有序
                if (nums[mid] < target && target <= nums[right]) {
                    // 目标值在右半部分
                    left = mid + 1;
                } else {
                    // 目标值在左半部分
                    right = mid - 1;
                }
            }
        }

        // 如果遍历结束仍未找到目标值，返回 -1
        return -1;
    }
};

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

在这里插入图片描述

一次二分

  • 时间复杂度：O(logn)，其中 n 为 nums 的长度。
  • 空间复杂度：O(1)，仅用到若干额外变量。
  • 最后一步return nums[left % nums.size()]; 这里取模的情况下，可以删去if (nums[0] <= nums.back()) return nums[0];
class Solution {
public:
    int findMin(vector<int>& nums) {
        // 如果数组的第一个元素小于或等于最后一个元素，说明数组没有旋转，
        // 或者是完全有序的（即使经过了完整的旋转），直接返回第一个元素。
        if (nums[0] <= nums.back()) return nums[0];

        // 初始化左右指针，用于二分查找最小值
        int left = 0, right = nums.size() - 1;
        
        // 记录原始数组的第一个元素作为基准值 m
        int m = nums[0];

        // 当 left <= right 时循环，即当搜索区间有效时进行二分查找
        while (left <= right) {
            // 计算中间位置，避免使用 (left + right) / 2 来防止可能的整数溢出
            int mid = left + (right - left) / 2;

            // 如果中间值大于或等于基准值 m，说明最小值在右半部分，更新 left
            if (nums[mid] >= m) {
                left = mid + 1;
            } 
            // 如果中间值小于基准值 m，说明最小值在左半部分（包括当前位置），更新 right
            else {
                right = mid - 1;
            }
        }

        // 循环结束时，left 指向的就是最小值的位置
        // 注意：这里假设输入数组至少有一个元素，并且是一个旋转排序数组
        return nums[left % nums.size()]; // 使用模运算处理 left 可能超出数组范围的情况
    }
};

4. 寻找两个正序数组的中位数在这里插入图片描述

log(min(m,n)) 做法

在这里插入图片描述

我的代码

  • 做法过于抽象
  • 请参考题解

官方题解
高赞题解

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size())
            return findMedianSortedArrays(nums2, nums1);

        int m = nums1.size(), n = nums2.size();

        int left = 0, right = m ;

        double maxLeft = 0, minRight = 0;

        while (left <= right) {

            int i = left + (right - left) / 2;
            int j = (m + n + 1) / 2 - i;

            int nums1i_1 = i == 0? INT_MIN:nums1[i-1];
            int nums1i = i==m ? INT_MAX:nums1[i];
            int nums2j_1 = j == 0? INT_MIN: nums2[j-1];
            int nums2j = j==n? INT_MAX:nums2[j];

            if(nums1i_1 <= nums2j)
            {
                minRight = min(nums1i,nums2j);
                maxLeft = max(nums1i_1,nums2j_1);

                left = i + 1 ;// i要继续增大
            }
            else
            {
                right = i - 1; //i要减小
            }
        }

        return (m+n)%2 == 0? (maxLeft + minRight) / 2.0 : maxLeft;
    }
};

log（m+n） 做法 （相当于去找第K小的数）

在这里插入图片描述

官方题解

class Solution {
public:
    int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
        /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
         * 这里的 "/" 表示整除
         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
         * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
         * 这样 pivot 本身最大也只能是第 k-1 小的元素
         * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
         * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
         * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
         */

        int m = nums1.size();
        int n = nums2.size();
        int index1 = 0, index2 = 0;

        while (true) {
            // 边界情况
            if (index1 == m) {
                return nums2[index2 + k - 1];
            }
            if (index2 == n) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return min(nums1[index1], nums2[index2]);
            }

            // 正常情况
            int newIndex1 = min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = min(index2 + k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            }
            else {
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totalLength = nums1.size() + nums2.size();
        if (totalLength % 2 == 1) {
            return getKthElement(nums1, nums2, (totalLength + 1) / 2);
        }
        else {
            return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
        }
    }
};

标签：二分,right,target,nums,int,mid,查找,hot100,left
From： https://blog.csdn.net/qq_42681630/article/details/144231320

相关文章

  • 蓝桥杯二分题
    P1083[NOIP2012提高组]借教室题目描述在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接......
  • 根据元素ID遍历树形结构，查找到所有父元素ID [代码]
    functionfindParentIds(elementId,treeData){constparentIds=[];functiontraverse(node){if(node.id===elementId){returntrue;}if(node.children){for(constchildofnode.children){if(traverse(child))......
  • hot100-一刷-04子串(共3道题)
    560.和为K的子数组题目链接题目描述代码实现分析：暴力：还是有点技巧的，如果单纯暴力，外层fori循环遍历起始下标start，内层forj循环遍历末尾end，里面还需要个循环，计算从i加到j,最坏会到\(O(n^3)\)。考虑固定某一个边界，比如固定end，从end往前算。点击查看代码classSolution......
  • Binary Deque(二分)
    Slavichasanarrayoflength\(n\)consistingonlyofzeroesandones.Inoneoperation,heremoveseitherthefirstorthelastelementofthearray.WhatistheminimumnumberofoperationsSlavichastoperformsuchthatthetotalsumofthearrayi......
  • 牛客---HJ48 从单向链表中删除指定值的节点（用ArrayList模拟链表，因为方便查找操作）
    示例代码importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;//注意类名必须为Main,不要有任何packagexxx信息publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);......
  • hot100-一刷-03滑动窗口(共2道题)
    3.无重复字符的最长子串题目链接题目描述代码实现分析：因为是要连续的序列，使用滑动窗口+Set集合来判断即将要加入窗口右端的元素是已经在窗口中出现过。代码：classSolution{publicintlengthOfLongestSubstring(Strings){intans=0;//Set......
  • 数据结构实训——查找
    声明： 以下是我们学校在学习数据结构时进行的实训，如涉及侵权马上删除文章声明：本文主要用作技术分享，所有内容仅供参考。任何使用或依赖于本文信息所造成的法律后果均与本人无关。请读者自行判断风险，并遵循相关法律法规。一、实训类型  验证性实训二、实训目的与任务1．掌......
  • 502 二分答案
    //502二分答案.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///*http://oj.daimayuan.top/course/22/problem/61给一个序列a1,a2,…,an。你可以对这个序列进行操作，每次操作可以选择一个元素，把它加1，经过不超过k次操作之后，希望序列里面的最小值最大......
  • 二分查找
    [Algo]二分查找注：Algo系列基于左神算法教程，提供C++实现。1.经典算法//1.经典二分查找：给定有序序列，查找val，存在返回(任一)索引，否则返回-1intbinarySearch(constvector<int>&v,intval){if(v.size()==0)return-1;intleft=0,right=v.size()-1,m......
  • Java入门：21.System类，Runtime类，Arrays类的常用方法，二分查找算法
    1System类System.exit(0); //手动关闭应用程序​System.currentTimeMillis();//获得当前系统时间的毫秒数​System.out;//获得一个打印流，可以实现控制台打印System.out.print();//打印内容（不换行）System.out.println();//打印内容，并换行System.out.printf();//......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99