每日一题--二分法找数组中的数

【题目描述】

公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会的每位员工都有一张带有号码的抽奖券。现在，主持人从小到大依次公布 n 个不同的获奖号码，小唐看着自己抽奖券上的号码 win，无比紧张。

【输入格式】

第一行一个正整数n（2<n≤100），表示有n个获奖号码。

第二行包含n个正整数，之间用一个空格隔开，表示依次公布的n个获奖号码。

第三行一个正整数 win，表示小唐抽奖券上的号码。1≤获奖号码，win<10000。

【输出格式】

一行一个整数，如果小唐中奖了，表示中奖的是第几个号码；如果没有中奖，则为 0。

For example:

Input

Result

7
1 2 3 4 16 27 55
3

3

答案

#include <iostream>

using namespace std;

int main()
{
    int n,i,win,a[100];
    cin >> n;
    
    //输出部分
    for(i=0;i<n;i++)
    {
        cin >> a[i];
    }
    cin >> win;
    int left = 0,right = n-1;   //left存放第一个元素下表,right存放最后一个元素的下标
    int found = n;      //found标记找到的位置，初始化为n,表示没有找到
    
    //二分过程
    while(left <= right)
    {
        int mid = (left + right)/2;
    
        if(a[mid] == win)   //找到了标记位置并退出循环
        {
            found = mid;
            break;
        }
        if(win < a[mid])
        {
            right = mid-1; //win只能在左半部分
        }
        else if(a[mid] < win)
        {
            left = mid+1;
        }
    }
    
    //输出部分
    if(found !=n)
    {
        cout << found + 1 << endl;  //对应的下标加1输出第几个号码
    }
    else
    {
        cout << 0 << endl;
    }
    return 0;
}

• 注意该案例中数组是从0到n-1定义的，共有n个数
• 要在编程中考虑到0是第一个数
• 其实实际编程过程真的不想把0设为第一个数
• 怪麻烦的
• 不知道教程为啥要这样写