猿圈19年校招笔试题

(52) 2024-02-16 09:01:01

1.查找整数

题目描述:

给定一个非降序的整数数组,数组中包含重复数字(重复数字很多),给定任意整数二分查找,返回数组正确的位置,给出函数实现。
a.连续相同的数字,返回最后一个匹配的位置。
b.如果数字不存在返回-1。

输入描述:

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

输出描述:

按题目描述输出。

示例:

输入:

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
THE END

发表回复