HBU月考二分查找（20分）

本文連結：https://blog.csdn.net/weixin_42449444/article/details/85621946

題目描述：

利用二分查找找出所給出的數在數組中的下标。

輸入格式:

第一行輸入n和m表示數組有n個資料，m表示要對m個數進行查找。

輸出格式:

所有輸出在一行完成，行末沒有多餘空格和多餘回車。

輸入樣例:

5 5
1 2 3 4 5
1 2 3 4 5

複制

輸出樣例:

0 1 2 3 4

複制

解題思路：

我先用Python寫的二分查找算法，送出代碼之後直接運作逾時。然後我用C++寫的二分查找算法，送出之後還是TLE！我嘞個去，Python逾時可以了解，C++寫的二分查找法還運作逾時就有點無語，流下TLE的淚水。然後我放棄二分查找法了，直接無腦用map，map的key值記錄資料，value值記錄這個資料所在的下标。送出之後還是TLE！于是我加上一條ios::sync_with_stdio(false);語句來取消cin和stdin的同步以減少程式的運作時間，送出代碼依舊TLE。無FK說，那我把cout改成printf來減少運作時間好吧，诶喲喂，送出之後完美AC，雖然這題要求的是用二分查找算法求解但是TLE我也沒辦法啊。

Py二分查找算法：部落格連結（之前寫過的代碼）

def search(data, item):
    start, end = 0, len(data) - 1
    
    while start <= end:
        middle = (start + end) // 2
        #縮小搜尋範圍
        if item < data[middle]:
            end = middle - 1
        elif item > data[middle]:
            start = middle + 1
        else:
            return middle
    #若沒找到,則傳回-1
    return -1

複制

C++AC代碼：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);    //取消cin和stdin的同步
    int n,m;
    cin >> n >> m;
    map<int,int> mp;     //mp的key值記錄資料，value值記錄該資料的所在下标
    for(int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        mp[temp] = i;
    }
    bool isVirgin = true;    //判斷是不是第一次
    for(int i = 0; i < m; i++)
    {
        int temp;
        cin >> temp;
        if(isVirgin)
        {
            printf("%d",mp[temp]);
            isVirgin = false;
        }
        else
        {
            printf(" %d",mp[temp]);
        }
    }
    return 0;
}

複制

HBU月考 二分查找（20分）