题解 - [入门]二分查找 - 核OJ

8

hetao668132 LV 10 @ 2023-8-25 21:24:10

此题解共出示三种方法：

二分查找

#include <iostream>
using namespace std;
int a[100000005],x,l,r,mid,n,ans;
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    cin >> x;
    l=1;
    r=n;
    while (l<=r)
    {
        mid=(l+r)/2;
        if(a[mid]>=x)
        {
            r=mid-1;
            ans=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    if(a[ans]==x)
    {
        
        cout <<ans;
    }
    else
    {
        cout << -1;
    }
    return 0;
}

递归（递归函数核心代码）

int f(int l, int r, int key)
{
    int mid = (l + r) / 2;
    if (l > r)
    {
        return -1;
    }
    else if (a[mid] == x)
    {
        return mid;
    }
    else if (a[mid] > x)
    {
        return f(l, mid - 1, key);
    }
    else
    {
        return f(mid + 1, r, key);
    }    
}

暴力枚举

面对这道基础题，我的好奇心被勾起，用暴力枚举是否超时（大家当彩蛋看看笑笑就行了）

计算机一秒大约可以计算10^8次

n<=10^6 10^6*2远远小于10^8

理论存在，实践开始！

#include <iostream>
using namespace std;
int a[100000005],x,l,r,mid,n,flag;
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    cin >> x;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==x)
        {
            cout << i;
            flag=1;
        }
    }
    if(!flag)
    {
        cout << -1;
    }
    return 0;
}

AC！！！

感谢观看，求赞(ﾉ*･ω･)ﾉ

hetao3573690 @ 2023-10-29 9:59:07

666

8

hetao2909413 LV 10 @ 2022-12-7 15:38:54

#include <iostream>
using namespace std;
const int N = 1000005;
int n, x, a[N];
int find(int l, int r)
{
    if (l + 1 == r)
        return r;
    int mid = l + r >> 1;
    if (a[mid] < x)
        l = mid;
    else
        r = mid;
    return find(l, r);
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i += 1)
        cin >> a[i];
    cin >> x;
    if (a[find(-1, n)] == x)
        cout << find(-1, n) + 1;
    else
        cout << -1;
    return 0;
}
//已AC,请放心食用~~

6

wsy1998 LV 10 MOD @ 2021-12-28 15:05:02

这里给出递归版：

int f(int l, int r, int key)
{
    int mid = (l + r) / 2;
    if (l > r)
        return -1;
    if (a[mid] == x)
        return mid;
    if (a[mid] > x)
        return f(l, mid - 1, key);
    if (a[mid] < x)
        return f(mid + 1, r, key);
}

3

hetao1846737 LV 10 @ 2023-9-24 16:09:54

就是不用二分~~

诶，你能拿我怎么样？

（〃｀ 3′〃）

#include <iostream>
using namespace std;
int main()
{
    int x,n;
    bool flag=0;
    cin>>n;
    int a[n+1];
    for (int i=1;i<=n;i++)cin>>a[i];
    cin>>x;
    for (int i=1;i<=n;i++)
    {
        if (a[i]==x)
        {
            cout<<i;
            flag=1;
        }
    }
    if (flag==0)cout<<-1;
    return 0;
}

2

hetao1678197 LV 10 @ 2023-6-25 21:24:02

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    int l, r, ans;
    l = 1;
    r = n;
    ans = -1;
    while (l <= r){
        int mid = (l + r) / 2;
        if (a[mid] <= m){
            l = mid + 1;
            ans = mid;
        }else{
            r = mid - 1;
        }
    }
    if (a[ans] == m)
        cout << ans;
    else  
        cout << -1;
}

0

hetao4976191 LV 10 @ 2023-7-20 17:35:56

#include <cstdio>
using namespace std;
int main(){
    int l,r,mid,pos,n,x,a[1000001];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    scanf("%d",&x);
    l=1,r=n,pos=-1;
    while(l<=r){
        mid=(l+r)/2;
        if(a[mid]==x){
            pos=mid;
            break;
        }else if(a[mid]<x)l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",pos);
    return 0;
}

0

hetao1443689 LV 9 @ 2023-6-21 15:42:39

#include <bits/stdc++.h>
using namespace std;
int n, a[1000005], x, l, r, mid, ans;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cin >> x;
    l = 0;
    r = n;
    ans = n + 1;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (a[mid] == x)
        {
            ans = mid;
            break;
        }
        else if (a[mid] < x)
        {
            l = mid + 1;
        }
        else if (a[mid] > x)
        {
            r = mid - 1;
        }
    }
    if (a[ans] == x)
    {
        cout << ans;
    }
    else if (ans == n + 1){
        cout << "-1";
    }//已AC，请放心使用
    return 0;
}

0

hetao2909373 LV 9 @ 2023-4-18 10:48:15

这道题就是简单的二分，不需要动太多脑子。

#include <bits/stdc++.h>
using namespace std;
int n, a[1000005], x, l, r, mid, ans;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cin >> x;
    l = 0;
    r = n;
    ans = n + 1;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (a[mid] == x)
        {
            ans = mid;
            break;
        }
        else if (a[mid] < x)
        {
            l = mid + 1;
        }
        else if (a[mid] > x)
        {
            r = mid - 1;
        }
    }
    if (a[ans] == x)//这里需要多判断一步，如果找到了x所在的位置，需要输出
    {
        cout << ans;
    }
    else if (ans == n + 1)//如果ans还是等于原来的数，说明数组里没有x这个数，while循环里没有改过ans的值，就输出-1
    {
        cout << "-1";
    }
    return 0;
}

hetao1678197 @ 2023-6-25 21:06:46

ans是不是可以直接等于-1？

-1

hetao8951299 LV 10 @ 2023-3-14 19:55:14

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,l,r,mid,a[1000005],x,ans;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cin>>x;
    l=1;
    r=n;
    ans=n+1;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(a[mid]==x)
        {
             ans=mid;
             break;
        }
        else if(a[mid]<x)
        {
             l=mid+1;
        }
        else
        {
             r=mid-1;
        }
   }
   if(a[ans]==x)
   {
       cout<<ans;
   }
   else
   {
       cout<<"-1";
   }
}

-1

hetao369939 LV 10 @ 2022-12-20 13:59:45

用课里最原始的方法就可以，不过不要忘记加上判断。（UP AC，请放心食用）

#include <iostream>
using namespace std;
int a[1000005], n, k, l, r, mid, ans;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cin >> k;
    l = 1;//l和r表示查找的范围，
    r = n;//左端点为1，右端点为n
    ans = n + 1;//ans表示最终答案 初始化为n+1
    while (l <= r)
    {
        mid = (l + r) / 2;//mid表示中间位置 即(l+r)/2
        if (a[mid] == k)
        {
            ans = mid;//当a[mid]等于k 表示找到了答案
            break;//把ans赋值为mid 并用break结束循环
        }
        else if (a[mid] < k)
        {
            l = mid + 1;//当a[mid]小于k 表示答案在mid右边 
                        //把l赋值为mid+1 到右边继续查找
        }
        else
        {
            r = mid - 1;//当a[mid]大于k 表示答案在mid右边
                        //把r赋值为mid-1 到左边继续查找
        }
    }
    if (a[ans] == k)
    {
        cout << ans;
    }
    else
    {
        cout << -1;
    }
    return 0;
}

-1

陆梓昱 LV 10 @ 2022-8-21 15:06:08

while(l<=r)
{
    int mid=(l+r)/2;
    if (a[mid]==x)
    {
        ans=mid;
        break;
    }
    else if (a[mid]<x)
    {
        l=mid+1;
    }
    else
    {
        r=mid-1;
    }
}

-2

fuyuxiang @ 2022-8-20 16:20:40

#include<iostream>
using namespace std;
int x, a[100005];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        
    }
    cin >> x;
    bool flag = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == x)
        {
            cout << i;
            flag = 1;
            break;
        }
    }
    if (!flag)
    {
        cout << "-1";
    }   
    return 0;
}
</span>

hetao8951299 @ 2023-3-14 19:51:13

这道题是让我们用二分查找来做的

-3

mayuying LV 9 SU @ 2022-4-24 16:11:15

鼓励大家写题解，但注意题解格式。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
}

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

-5

hetao10740195 LV 9 @ 2022-10-3 17:14:32

> 请问老师为什么我的代码不过

> #include<iostream>
> using namespace std;
> int a[100005], n, x, l, r, mid, ans;
> int main()
> ``{
> cin >> n;
> for (int i = 1; i <= n; i++)
> {
> cin >> a[i];
> }
> cin >> x;
> l = 1;
> r = n;
> ans = -1;
> while(l<=r)
> {
> int mid=(l+r)/2;
> if (a[mid]==x)
> {
> ans=mid;
> break;
> }
> else if (a[mid] {
> l=mid+1;
> }
> else
> {
> r=mid-1;
> }
> }
> cout << ans;
> return 0;
> }

hetao369939 @ 2022-12-20 14:42:42
啊因为你最后没有判断哦~

把这段加上↓
```
if (a[ans] == k)
{
    cout << ans;
}
else
{
    cout << -1;
}
```
hetao2909413 @ 2023-2-9 14:48:07

你太美
hetao1443689 @ 2023-6-21 15:45:05

@ 或在前面+ans=-1
hetao1678197 @ 2023-6-25 21:09:00
hetao1678197 @ 2023-6-25 21:10:11

-5

wsy1998 LV 10 MOD @ 2022-4-19 22:50:26

严禁抄题解，发现后取消成绩

15 条题解

此题解共出示三种方法：

二分查找

递归（递归函数核心代码）

暴力枚举

```cpp

```

[入门]二分查找

信息

状态

开发

支持

15 条题解

此题解共出示三种方法：

二分查找

递归（递归函数核心代码）

暴力枚举

```cpp

```

[入门]二分查找

信息

状态

开发

支持

还没有账户？

登录