首页 > 其他分享 >二分法

二分法

时间:2024-04-01 20:11:28浏览次数:23  
标签:right target nums int mid 二分法 left

概述

二分查找详解.md

STL C++ 二分查找库

二分查找库

闭区间、左闭右开区间和开区间

视频讲解二分法

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)
                left = mid + 1; // 范围缩小到 [mid+1, right]
            else
                right = mid - 1; // 范围缩小到 [left, mid-1]
        }
        return left; // 或者 right+1
    }

    // 左闭右开区间写法
    int lower_bound2(vector<int> &nums, int target) {
        int left = 0, right = nums.size(); // 左闭右开区间 [left, right)
        while (left < right) { // 区间不为空
            // 循环不变量:
            // nums[left-1] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1; // 范围缩小到 [mid+1, right)
            else
                right = mid; // 范围缩小到 [left, mid)
        }
        return left; // 或者 right
    }

    // 开区间写法
    int lower_bound3(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)
                left = mid; // 范围缩小到 (mid, right)
            else
                right = mid; // 范围缩小到 (left, mid)
        }
        return right; // 或者 left+1
    }

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};
        // 如果 start 存在,那么 end 必定存在
        int end = lower_bound(nums, target + 1) - 1;
        return {start, end};
    }
};

作者:灵茶山艾府
链接:https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/1980196/er-fen-cha-zhao-zong-shi-xie-bu-dui-yi-g-t9l9/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

题目

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

二分法写作技巧:

1、首先 while (left <= right) 怎么写取决于,left right 是闭区间还是开区间。
2、mid = (left + right) / 2; 这个是不影响的,所有区间都这么写
3、将三种方法写全,不要偷懒 。一开始我的 == 情况没有分开写导致了一大堆的问题

使用 STL 库

    vector<int> searchRange(vector<int> &nums, int target) {
        auto bound =  equal_range(nums.begin(), nums.end(), target);
        int left = bound.first - nums.begin();
        int right = bound.second - nums.begin();
        return {left, right};
    }

我的解题思路

我的思路:
1、寻找第一个小于。当等于的时候,继续往左移。而不是 直接退出。知道找到最左一个满足条件的值
2、寻找第一个大于,跟1一样。

我的代码


#include "vector"
#include "set"
#include "iostream"
#include "algorithm"
#include "tuple"
#include "unordered_map"

using namespace std;

class Solution {
public:
    // 找到左边第一个
    int find_first(vector<int> &nums, int target) {
        int result = -1;
        int left = 0;
        int right = nums.size() - 1;
        int mid = 0;
        while (left <= right) { // 在闭区间之中寻找 [left, right]
            mid = (left + right) / 2;
            if (nums[mid] == target){
                result = mid;
                right = mid -1 ; // 当找到一个时,继续往左边寻找
            }else if (nums[mid] > target) {
                right = mid -1 ;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        return result;

    }

    //    找到右边最后一个
    int find_last(vector<int> &nums, int target) {
        int result = -1;
        int left = 0;
        int right = nums.size() - 1;
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target){
                result = mid;
                left = mid + 1;
            }else if (nums[mid] > target) {
                right = mid -1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        return result;
    }

    vector<int> searchRange(vector<int> &nums, int target) {
        int left = find_first(nums, target);
        int right = find_last(nums, target);
        if (nums.size() == 0 || left > right) {
            return {-1, -1};
        }
        return {left, right};
    }
};

int main() {
    std::cout << "Hello, World!" << std::endl;
    Solution *a = new Solution();
    vector<int> nums = {5, 7, 7, 8, 8, 10};
    a->searchRange(nums, 8);
    return 0;
}


704. Binary Search 704. 二分查找

标签:right,target,nums,int,mid,二分法,left
From: https://www.cnblogs.com/spindrift/p/18109279

相关文章

  • 代码随想录第一天-双指针+二分法
    参考资源:https://programmercarl.com/、ChatGPT3.5语言:Java二分法二分法,又称为二分查找或折半查找,是一种在有序数组中查找目标值的算法。它的基本思想是将目标值与数组中间的元素进行比较,若目标值等于中间元素,则查找成功;若目标值小于中间元素,则在数组的左半部分继续查......
  • 3月22日二分法查找
    二分查找:二分查找也叫折半查找,二分查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。普通查找的时间复杂度为O(n),二分查找的时间复杂度仅需要O(log2^n)查找的实现原理:先定左右边界,之后比较待查找元素与中间元素谁大谁小,如果中间值大于目标值,那么右边界等于中......
  • [数组练习题]二分法查找操作实例:使用二分法查找有序数组中元素。 找到返回索引,不存在
    文章目录题干一、题目分析1.定义数组,用于后续在数组中查找元素2.对数组进行排序3.定义方法4.调用方法,打印输出二、代码1.代码块2.一图流总结题干提示:这段是题干,仔细阅读仔细分析:二分法查找操作:使用二分法查找有序数组中元素。找到返回索引,不存在输出-1。......
  • Python 递归函数实现二分法,带思路解释
            二分法可以大大提升对有序数列的查找,传统的迭代查找会挨个比较数列中的值,如果数列较为庞大会影响查询效率。二分法每次取数列的中间数与待查找数字比较大小,以升序排列为例子 首先要考虑数列长度的奇偶性。        奇数取中间位置的数字,如果比待查找......
  • 【二分法】分巧克力问题/python
    1.看出是用二分法:最大值最小化,最小值最大化,满足条件的最值,用二分法做。2.确定low,high,确定check的条件3.注意: 是当low<high的时候进行循环,当相等或大于的时候输出,while的条件不能写错。 本题是在区间里面找满足条件的最大值,所以,在算mid的时候面对取整的问题让它向大......
  • 二分法
    通往奥格瑞玛的道路(洛谷P1462)题目大意无向图中每走一条路会遭受攻击损失一定血量,当血量为负时则无法到达,每到一个城市都会收取一定费用包括起点和终点。现求在能到达终点的所有方案中找出城市缴费最多的一次中的最小值。解题思路二分法+dijkstra,二分城市缴纳费用查找节点。......
  • C语言实现二分法
    现在有一个任务:从一堆有序数字中找出其中一个数字有两种方法1)从头到尾依次寻找2)从该些数字中中间部位比较若小于要找数字则在后半部分否则在前半部分再进行这样的方式进行循环,直至找到或找不到此数字现介绍这样的方法——二分法在计算机科学中,二分搜索(英语:binarysearch),也称折半搜......
  • Leetcode刷题第五天-二分法-回溯
    215:第k个最大元素链接:215.数组中的第K个最大元素-力扣(LeetCode)em~~怎么说呢,快速选择,随机定一个目标值,开始找,左边比目标小,右边比目标大,左右同时不满足时,交换左右位置,直到左指针比右指针大,交换目标和右指针位置的值,此时右指针位置即时目标值的在排序好数组中的位置,如果k在右......
  • Leetcode刷题第四天-双指针-二分法
    15:三个数之和链接:15.三数之和-力扣(LeetCode)em...双冲for循环,从头去遍历,0-(a+b)是否在列表中,最终timeout数组从小到大排序,设置三个指针,i从头遍历到lens-1,j从i+1开始,k从lens-1开始,sums==0,放入结果,大于0,k-1,小于0,j+1如果i和i+1比较,相同跳过的话,会丢结果,i和i-1相等跳过,因为i-1已......
  • C# 二分法查询代码
    二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。使用二分法的前提条件是:在有序数组中查找特定元素publicstaticintSearchInsert(int[]nums,inttarget){intstart=0;//开始索引intend=nums.Length-1;//结束索引i......