PTA:二分查找法

时间:2025-03-14 07:04:50

题目

用二分法在一个有序数列{1,2,3,4,5,6,7,8,9,10}中查找key值,若找到key则输出其在数组中对应的下标,否则输出not found。

输入格式:
直接输入一个要查找的正整数key。没有其它任何附加字符。

输出格式:
找到则在一行中按照“weizhi:下标”的格式输出其在数组中对应的下标,否则输出not found。

输入样例:
4
输出样例:
weizhi:3
输入样例:
15
输出样例:
not found

解题过程

#include <bits/stdc++.h>

using namespace std;

int BinarySearch(int *p, int n, int x);

int main()
{
    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};   
    int x;
    cin >> x;
    int m;
    m = BinarySearch(a, 10, x);
    if (m >= 0)
        cout << "weizhi:" << m;
    else
        cout << "not found";
}

int BinarySearch(int *p, int n, int x)
{
    int low, mid, high;  
    low = 0; 
    high = n - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (x == p[mid])   
            return mid;
        else if (x < p[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;  
}