力扣704. 二分查找

题目

给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。

示例一

1
2
3

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例二

1
2
3

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

思路

这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件。

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

题解

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();
        while (left < right) {
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
};

计蒜客T1560. 二分查找（一）

题目

蒜头君手上有个长度为 $n$ 的数组 $A$ 。由于数组实在太大了，所以蒜头君也不知道数组里面有什么数字，所以蒜头君会经常询问整数 $x$ 是否在数组 $A$ 中。

输入格式

第一行输入两个整数 $n$ 和 $m$ ，分别表示数组的长度和查询的次数。

接下来一行有 $n$ 个整数 $a_{i}$ 。

接下来 $m$ 行，每行有 1 个整数 $x$ ，表示蒜头君询问的整数。

输出格式

对于每次查询，如果可以找到，输出"YES"，否则输出"NO"。

数据范围

$1\leqslant n,m\leqslant 10^{5},0\leqslant x\leqslant 10^{6}。$

样例

10 5
1 1 1 2 3 5 5 7 8 9
0
1
4
9
10

NO
YES
NO
YES
NO

题解

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

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

int main()
{
    int n, m;
    
    cin >> n >> m;
    
    vector<int> v;
    
    for (int i = 0; i < n; i++)
    {
        int x;
        
        cin >> x;
        
        v.push_back(x);
    }
    
    sort(v.begin(), v.end());
    
    for (int i = 0; i < m; i++)
    {
        int x;
        
        cin >> x;
        
        if (search(v, x) != -1)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    
    return 0;
}

计蒜客T1561. 二分查找（二）

题目

蒜头君手上有个长度为 $n$ 的数组 $A$ 。由于数组实在太大了，所以蒜头君也不知道数组里面有什么数字，所以蒜头君会经常询问在数组 $A$ 中，大于等于 $x$ 的最小值是多大？

输入格式

第一行输入两个整数 $n$ 和 $m$ ，分别表示数组的长度和查询的次数。

接下来一行有 $n$ 个整数 $a_{i}$ 。

接下来 $m$ 行，每行有 1 个整数 $x$ ，表示蒜头君询问的整数。

输出格式

对于每次查询，如果可以找到，输出这个整数。

否则输出 −1。

数据范围

$1\leqslant n,m\leqslant 10^{5},0\leqslant x\leqslant 10^{6}。$

样例

10 5
1 1 1 2 3 5 5 7 8 9
0
1
4
9
10

题解

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

int lower_bound(vector<int> &nums, int k)
{
    int left = 0, right = nums.size() - 1;
    while (left < right)
    {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= k)
            right = mid;
        else
            left = mid + 1;
    }
    if (nums[left] < k)
        left++;
    return left;
}

int main()
{
    int n, m;

    cin >> n >> m;

    vector<int> v;

    for (int i = 0; i < n; i++)
    {
        int x;

        cin >> x;

        v.push_back(x);
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < m; i++)
    {
        int x;

        cin >> x;

        int p = lower_bound(v, x);

        if (p > v.size() - 1)
        {
            cout << "-1" << endl;
        }
        else
        {
            cout << v[p] << endl;
        }
    }

    return 0;
}

计蒜客T1562. 二分查找（三）

题目

蒜头君手上有个长度为 $n$ 的数组 $A$ 。由于数组实在太大了，所以蒜头君也不知道数组里面有什么数字，所以蒜头君会经常询问在数组 $A$ 中，比 $x$ 大的最小值是多大？但是这次蒜头君要求这个数字必须大于 $x$ ，不能等于 $x$ 。

输入格式

第一行输入两个整数 $n$ 和 $m$ ，分别表示数组的长度和查询的次数。

接下来一行有 $n$ 个整数 $a_{i}$ 。

接下来 $m$ 行，每行有 1 个整数 $x$ ，表示蒜头君询问的整数。

输出格式

对于每次查询，如果可以找到，输出这个整数。

否则输出 −1。

数据范围

$1\leqslant n,m\leqslant 10^{5},0\leqslant x\leqslant 10^{6}。$

样例

10 5
1 1 1 2 3 5 5 7 8 9
0
1
4
9
10

题解

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

int upper_bound(vector<int> &nums, int k)
{
    int left = 0, right = nums.size() - 1;
    while (left < right)
    {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] > k)
            right = mid;
        else
            left = mid + 1;
    }
    if (nums[left] <= k)
        left++;
    return left;
}

int main()
{
    int n, m;

    cin >> n >> m;

    vector<int> v;

    for (int i = 0; i < n; i++)
    {
        int x;

        cin >> x;

        v.push_back(x);
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < m; i++)
    {
        int x;

        cin >> x;

        int p = upper_bound(v, x);

        if (p > v.size() - 1)
        {
            cout << "-1" << endl;
        }
        else
        {
            cout << v[p] << endl;
        }
    }

    return 0;
}

计蒜客T1563. 二分查找（四）

题目

蒜头君手上有个长度为 $n$ 的数组 $A$ 。由于数组实在太大了，所以蒜头君也不知道数组里面有什么数字，所以蒜头君会经常询问在数组 $A$ 中，等于 $x$ 的数字有多少个？

输入格式

第一行输入两个整数 $n$ 和 $m$ ，分别表示数组的长度和查询的次数。

接下来一行有 $n$ 个整数 $a_{i}$ 。

接下来 $m$ 行，每行有 1 个整数 $x$ ，表示蒜头君询问的整数。

输出格式

对于每次查询，输出一个整数，表示数组 $A$ 中有多少个 $x$ 。

数据范围

$1\leqslant n,m\leqslant 10^{5},0\leqslant x\leqslant 10^{6}。$

题解

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

int lower_bound(vector<int> &nums, int k)
{
    int left = 0, right = nums.size() - 1;
    while (left < right)
    {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= k)
            right = mid;
        else
            left = mid + 1;
    }
    if (nums[left] < k)
        left++;
    return left;
}

int upper_bound(vector<int> &nums, int k)
{
    int left = 0, right = nums.size() - 1;
    while (left < right)
    {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] > k)
            right = mid;
        else
            left = mid + 1;
    }
    if (nums[left] <= k)
        left++;
    return left;
}

int main()
{
    int n, m;

    cin >> n >> m;

    vector<int> v;

    for (int i = 0; i < n; i++)
    {
        int x;

        cin >> x;

        v.push_back(x);
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < m; i++)
    {
        int x;

        cin >> x;

        cout << upper_bound(v, x) - lower_bound(v, x) << endl;
    }

    return 0;
}

计蒜客T1555. 二分查找（五）

题目

蒜头君手上有个长度为 $n$ 的数组 $A$ 。由于数组实在太大了，所以蒜头君也不知道数组里面有什么数字，所以蒜头君会经常询问在数组 $A$ 中，小于等于 $x$ 的最大值是多大？

输入格式

第一行输入两个整数 $n$ 和 $m$ ，分别表示数组的长度和查询的次数。

接下来一行有 $n$ 个整数 $a_{i}$ 。

接下来 $m$ 行，每行有 1 个整数 $x$ ，表示蒜头君询问的整数。

输出格式

对于每次查询，如果可以找到，输出这个整数。

否则输出 −1。

数据范围

$1\leqslant n,m\leqslant 10^{5},0\leqslant x\leqslant 10^{6}。$

样例

10 5
1 1 1 2 3 5 5 7 8 9
0
1
4
9
10

题解

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

int search(vector<int> &nums, int target)
{
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right)
    {
        int middle = left + ((right - left) / 2);
        if (nums[middle] > target)
        {
            right = middle - 1;
        }
        else
        {
            left = middle + 1;
        }
    }

    return left - 1;
}

int left_bound(vector<int> &nums, int target)
{
    int left = 0;
    int right = nums.size();

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

    if (left == nums.size())
        return nums.size() - 1; // 根据题意，大于所有值则答案为数组的最大值
    return nums[left] > target ? left - 1 : left;
}

int main()
{
    int n, m;

    cin >> n >> m;

    vector<int> v;

    for (int i = 0; i < n; i++)
    {
        int x;

        cin >> x;

        v.push_back(x);
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < m; i++)
    {
        int x;

        cin >> x;

        int p = left_bound(v, x);

        if (p == -1)
        {
            cout << "-1" << endl;
        }
        else
        {
            cout << v[p] << endl;
        }
    }

    return 0;
}

二分查找题解

力扣704. 二分查找

题目

思路

题解

计蒜客T1560. 二分查找（一）

题目

输入格式

输出格式

数据范围

样例

题解

计蒜客T1561. 二分查找（二）

题目

输入格式

输出格式

数据范围

样例

题解

计蒜客T1562. 二分查找（三）

题目

输入格式

输出格式

数据范围

样例

题解

计蒜客T1563. 二分查找（四）

题目

输入格式

输出格式

数据范围

题解

计蒜客T1555. 二分查找（五）

题目

输入格式

输出格式

数据范围

样例

题解