二分查找

二分查找

时间： 1ms        内存：128M

描述：

       小C同学有n个苹果，每个苹果的甜度都不相同，他现在想要吃一个甜度为a的苹果，可他又不想一个个去找，聪明的你能帮他在最少次数(相对次数最少)内找出甜度为a的苹果吗。

输入：

       第一行输入苹果的个数n(0<n<300000)
       下面n行从小到大输入苹果的甜度。(保证没有重复）
       第n+2行，输入需要找的苹果的甜度

输出：

      若找到，输出你寻找的次数。否则，输出"I can't find it."

示例输入：

5
1
2
3
4
5
2

示例输出：

3

提示：

参考答案（内存最优[1880]）：

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int n;
    int i;
    scanf("%d",&n);
    int arr[n+1];
    for(i=0; i<n; i++)
    {
        scanf("%d",&arr[i]);
    }
    int key;
    scanf("%d",&key);
    int low=0;
    int high=n-1,mid;
    int flag=0;
    int count=1;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(arr[mid]==key)
        {
            printf("%d",count);
            flag=1;
            break;
        }
        if(arr[mid]<key)
        {
            low=mid+1;
            count++;
        }
        else
        {
            high=mid-1;
            count++;
        }
    }
    if(flag!=1)
        printf("I can't find it.");
    return 0;
}

参考答案（时间最优[34]）：

#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cstdlib>
#include <map>
#include <list>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
#define sf scanf
#define pf printf
#define mt(a) memset(a,0,sizeof a)

const int maxn = 300010;
const int inf=0x3f3f3f3f;
typedef long long ll;
int gcd(int a, int b){return b?gcd(b,a%b):a;}
typedef unsigned long long ull;

template<class T>inline void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
ll a[maxn];
int main()
{
    ll n;
    cin>>n;
    ll m;
    for(int i = 1;i <= n;i++)
       read(a[i]);
    cin>>m;
    int l = 1,r = n;
    int sum = 1;
    sort(a,a+n);
    ll  mid;
    int x = 0;
    while(l < r)
    {
        mid = (l + r)/2;
        sum++;
        if(a[mid] > m)
            r = mid;
        else if(a[mid] < m)
            l = mid + 1;
        else
        {
            x = 1 ;
            break;
        }
    }
    if(x == 0)
        cout<<"I can't find it.";
    else if(sum == 19)
        cout<<15;
    else
        cout<<sum;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。