每日一练——查找整数

题目描述

给定一个非降序的整数数组，数组中包含重复数字（重复数字很多） ，给定任意整数，对数组进行二分查找，返回数组正确的位置，给出函数实现。 a. 连续相同的数字，返回最后一个匹配的位置 b. 如果数字不存在返回 -1。（测试用例仅做参考，我们会根据代码质量进行评分）

输入描述：

第一行给定数组长度n,目标值tar。(1<=n,tar<=10000) 第二行给出n个整数a.(1<=a<=10000)

输出描述：

按题目描述输出。

输入：
7 4
1 2 2 3 4 4 10
输出：
5

题解：

二分查找的变种，在二分查找中添加一点约束条件即可。

答案代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

int Binary_Search(int *a,int n,int key)
{
    int low,high,mid;
    low=1;
    high=n;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(key<a[mid])
            high=mid-1;
        if(key>a[mid])
            low=mid+1;
        else if(key == a[mid]){    //对相同元素的处理
            for(int i=mid; i<=n; i++){
                if(key != a[i])
                    return i-1;
            }
        }

    }
    return -1;
}

int main()
{
    int n,tar,res;
    int a[10005];
    scanf("%d%d",&n,&tar);
    for(int i=0; i<n; i++){
        scanf("%d", &a[i]);
    }
    sort(a,a+n);
    res = Binary_Search(a,n,tar);
    printf("%d\n", res);
    return 0;
}