二分查找

[编程题]二分查找

热度指数：468 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

请实现有重复数字的有序数组的二分查找。

输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。

输入描述:

第一行两个正整数 、，分别表示数组长度与查找值。

第二行  个正整数 ，表示有序数组。

输出描述:

输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。

示例1

输入

5 4
1 2 4 4 5

输出

示例2

输入

5 4
1 2 3 3 5

输出

示例3

输入

5 4
1 2 2 3 3

输出

算法知识视频讲解

小宁lt

#include <iostream>
#include <vector>

using namespace std;

int binaryserch(vector<int>& nums,int target,int n)
{
    if(nums[n-1]<target)
    {
        return n+1;
    }
    int l=0,r=n-1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(nums[mid]<target)
        {
            l=mid+1;
        }
        else
        {
            r=mid;
        }
    }
     return l+1;
}

int main() 
{
   int n=0,v=0;
   cin>>n>>v;
   vector<int> nums;
   for(int i=0;i<n;i++)
   {
        int x;
        cin>>x;
        nums.push_back(x);
   }
   int ret=binaryserch(nums,v,n);
   cout<<ret;
}
// 64 位输出请用 printf("%lld")

编辑于 2023-12-03 19:54:00 回复(0)

元清加油

#include <iostream>
#include<vector>
using namespace std;

//二分查找
int BinarySearch(vector<int> arr, int target, int n)
{
    if (target > arr[n - 1])       //如果target大于最后一个数那么也就大于
    {
        return n + 1;
    }
    int left = 0;
    int right = n ;
    int mid = left + (right - left) / 2;
    while (left < right)
    {
        if (arr[mid] >= target)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }

        mid = (left + right) / 2;
    }
    return mid + 1;
}
int main()
{
    int n = 0;                      //数组长度
    int v = 0;                      //查找值
    cin >> n >> v;
    vector<int> arr;
    arr.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    cout << BinarySearch(arr, v, n);
}

发表于 2023-10-18 18:54:27 回复(0)