首页 > 试题广场 >

找出指定数在数组中的范围

[编程题]找出指定数在数组中的范围

热度指数：1368 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

输入一个排好序的整数数组，找到指定目标数的开始和结束位置。如果指定的数字不在数组中，则输出 [-1,-1]。例如，输入数组为[5, 7, 7, 8, 8, 10]，目标数为8, 输出[3, 4].本题会人工判题，要求时间复杂度O(logn)

输入描述:

输入数据包括两行:
 第一行两个整数n(1 ≤ n ≤ 10 ^ 5),和需要查找的数target
 第二行n个整数,范围均在32位整数内,以空格分隔

输出描述:

输出格式为[begin,end],如果不存在就输出[-1,-1]

示例1

输入

6 8 5 7 7 8 8 10

输出

3 4

算法知识视频讲解

WindedMan

//直接用二分法

//找到之后再在附近暴力搜素

#include<iostream>
using namespace std;

void FindTarget(int a[],int n,int target){
    int start=0,end=n-1,mid=0,tag=-1;
    while(start<=end){
        mid=(start+end)/2;
        if(a[mid]==target){tag=mid;break;}
        else if(a[mid]<target)start=mid+1;
        else end=mid-1;
    }
    if(tag==-1){
        cout<<"["<<-1<<","<<-1<<"]"<<endl;
        return ;
    }
    int num1=tag,num2=tag;
    for(int i=tag-1;i>=0;i--)
        if(a[i]==a[tag])num1--;
    else break;
    for(int i=tag+1;i<n;i++)
        if(a[i]==a[tag])num2++;
    else break;
    cout<<"["<<num1<<","<<num2<<"]"<<endl;
}
int main(){
    int n,target;
    cin>>n;
    cin>>target;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    FindTarget(a,n,target);
    return 0;
}

发表于 2020-02-17 22:15:15 回复(0)

更多回答

元气の悟空

#include<algorithm>
#include<stdio.h>
using namespace std;
int a[100005],n,i,target,l,r;
int main(){
    for(scanf("%d%d",&n,&target),i=0;i<n;i++) scanf("%d",&a[i]);
    int w=lower_bound(a,a+n,target)-a;
    if(w>=n||a[w]!=target) printf("[-1,-1]\n");
    else{
        for(l=0,r=n-1;l+1<r;){
            int mid=l+(r-l)/2;
            if(a[mid]<=target) l=mid;
            else r=mid;
        }
        printf("[%d,%d]\n",w,a[r]==target?r:l);
    }
}

发表于 2017-10-31 12:46:13 回复(0)

正在卷的三文鱼很讨厌吃香菜

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] line1=br.readLine().split(" ");
        int n=Integer.parseInt(line1[0]);
        int target=Integer.parseInt(line1[1]);
        String[] line2=br.readLine().split(" ");
        int[] nums=new int[n];
        for(int i=0;i<n;i++){
            nums[i]=Integer.parseInt(line2[i]);
        }
        int i=0,j=n-1;
        //这里是找到小于等于target的最大数
        while(i<j){
            int mid=(i+j+1)/2;
            if(nums[mid]<=target){
                i=mid;
            }else{
                j=mid-1;
            }
        }
        int l=0,h=n-1;
        //大于等于target的最小数
        while(l<h){
            int mid=(l+h)/2;
            if(nums[mid]>=target){
                h=mid;
            }else{
                l=mid+1;
            }
        }
        if(nums[i]!=target){
            System.out.println("[-1,-1]");
        }else{
            System.out.println("["+l+","+i+"]");
        }
    }
}

改进后的二分查找，找到小于等于target的最大数（上界），大于等于target的最小数（下界），注意最后还要检查是否存在

发表于 2019-08-20 19:16:11 回复(3)

职业浪子_

写的有点乱，就是用三次折半排序，复杂度为logn+2log（n/2）

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int sum = scanner.nextInt();

int nums[] = new int[n];

boolean flag = false;

for (int i = 0; i < n; i++) {

nums[i] = scanner.nextInt();

}

int Index;

int secondIndex = 0;

int firstIndex = 0;

Index = zheban(nums,sum,0,nums.length-1);

if(Index!=-1){

flag=true;

firstIndex = zheban1(nums,sum,0,Index);

secondIndex = zheban2(nums,sum,Index,nums.length-1);

}

System.out.println(flag?"["+firstIndex+","+secondIndex+"]":"[-1,-1]");

}

public static int zheban(int[] nums, int sum, int begin, int end){

if(begin<=end) {

int index = (end + begin) / 2;

if (nums[index] == sum) {

return index;

} else if (nums[index] < sum) {

return zheban(nums, sum, index + 1, end);

} else {

return zheban(nums, sum, begin, index - 1);

}

}else {

return -1;

}

public static int zheban1(int[] nums, int sum, int begin, int end){

if(begin<=end) {

int index = (end + begin) / 2;

if ((index > 0 && nums[index - 1] != sum && nums[index] == sum)||(index==0&&nums[index]==sum)) {

return index;

} else if (nums[index] == sum) {

return zheban1(nums, sum, begin, index - 1);

} else {

return zheban1(nums, sum, index + 1, end);

}

return end;

}

public static int zheban2(int[] nums, int sum, int begin, int end) {

if (begin < end) {

int index = (end + begin) / 2;

if ((index + 1 < nums.length && nums[index + 1] != sum && nums[index] == sum||(index==nums.length-1&&nums[index]==sum))) {

return index;

} else if (nums[index] == sum) {

return zheban2(nums, sum, index + 1, end);

} else {

return zheban2(nums, sum, begin, index - 1);

}

}return begin;

}

发表于 2017-08-31 22:23:38 回复(1)

切尔西是冠军

def binary_search(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        m = l + ((r - l) >> 1)
        if nums[m] < target:
            l = m + 1
        elif nums[m] > target:
            r = m - 1
        else:
            return m
    return l if nums[l] == target else -1

n, target = map(int, input().split())
nums = list(map(int, input().split()))
idx = binary_search(nums, target)
if idx == -1:
    print('[' + str(-1) + ',' + str(-1) + ']')
else:
    begin, end = idx, idx
    while begin>=0 and nums[begin] == target:
        begin -= 1
    while end<len(nums) and nums[end] == target:
        end += 1
    print('[' + str(begin+1) + ',' + str(end-1) + ']')

发表于 2020-03-30 17:06:01 回复(0)

daniuniuniuniu

b = input()
n = int(b.split()[0])
k = int(b.split()[1])

a = input()
data=list(map(int,a.split()))

### 初始化
left = 0
right = n-1
leftindex = rightindex = -1

### 寻找最左边的k的位置
while left<=right:
    mid = (left+right)//2
    if data[mid]<k:
        left = mid+1
    elif data[mid]>k:
        right = mid-1
    else:
        right = mid -1

        leftindex = mid

### 右边k的位置
left = 0
right = n-1

while left<=right:
    mid = (left+right)//2
    if data[mid]<k:
        left = mid+1
    elif data[mid]>k:
        right = mid-1
    else:
        left = mid +1
        rightindex = mid

print('['+str(leftindex)+','+str(rightindex)+']')

编辑于 2020-03-16 09:07:09 回复(0)

VV不吃香菜

//使用改进的二分查找：找到mig的值等于target之后，再左右分别遍历，找到begin end
import java.util.*;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] nums = sc.nextLine().split(" ");
        int n = Integer.parseInt(nums[0]);
        int target = Integer.parseInt(nums[1]);
        String[] arr = sc.nextLine().split(" ");
        int[] array = new int[n];
        for(int i =0;i<n;i++){
            array[i] = Integer.parseInt(arr[i]);
        }
        getBeginAndEnd(array,n,target);
    }
    public static void getBeginAndEnd(int[] array,int n,int target){
        if(n<0||array==null){
            return;
        } 
        int l=0;
        int h=n-1;
        int tag = -1;
        while(l<=h){
            int m = (l+h)/2;
            if(array[m]>target){
                h=m-1;
            }else if(array[m]<target){
                l=m+1;
            }else if(array[m]==target){
                tag=m;
                break;
            } 
        }
        if(tag==-1){
            System.out.println("["+-1+","+-1+"]");
            return;
        }else{
            int begin=tag;
            int end = tag;
            for(int i=begin-1;i>=0;i--){
                if(array[i]==array[tag]){
                    begin--;
                }else{
                    break;
                }
            }
            for(int i=end+1;i<n;i++){
                if(array[i]==array[tag]){
                    end++;
                }else{
                    break;
                }
            }
            System.out.println("["+begin+","+end+"]");
            return;
        }
    }
    
}

发表于 2020-03-02 23:51:37 回复(0)

Iceman96

这是一种不考虑时间复杂度的解法，将数组转化为字符串，再使用字符串的indexOf()和lastIndexOf()函数来找到开始和结束位置

import java.util.*;
public class Main {
    public static void main(String[] args) {
        int[] numTarget = new int[2];
        int index = 0;

        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] temp = str.split(" ");
        for (int i = 0; i < temp.length; i++)
            numTarget[i] = Integer.parseInt(temp[i]);
        str = sc.nextLine();
        temp = str.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String tmp:temp) {
            sb.append(tmp);
        }
        String string = sb.toString();
        int start = string.indexOf(numTarget[1] + "");
        int end = string.lastIndexOf(numTarget[1] + "");
        if (start == -1)
           System.out.println("[-1,-1]" );
        else
            System.out.println("[" + start + "," + end + "]");
    }
}

发表于 2019-09-08 12:22:27 回复(0)

C/C++

让让201902212045920

第一次写答案，可以AC，但是写的比较蠢，欢迎指正

自己感觉问题在于虽然搜索mid的时候是二分的，但是在找上下边界的时候复杂度还是O(n)

#include<iostream>
using namespace std;

void core(int a[], int left, int right, int target, int res[], int n)
{
	while (left <= right)
	{
        //特殊情况
        if (a[left] > target || a[right] < target)    //target不在数组中
			break;
        if(a[left] == target && a[right] == target)    //数组所有值相等
        {
            res[0] = left;
            res[1] = right;
            break;
        }
        //常规情况
		int mid = (right + left) / 2;

		if (a[mid] < target)
			left = mid + 1;
		else if (a[mid] > target)
			right = mid - 1;
		else
		{
			left = mid + 1;	
            right = mid;
			res[0] = mid;
			res[1] = mid;
			while (a[res[0]] == target && res[0]>=0)
				res[0]--;
			while (a[res[1]] == target && res[1]<=n-1)
				res[1]++;
			res[0]++;//上面的while会多算一次，要减掉，res[1]同理
            res[1]--;
		}
	}
}

int main()
{
	int n, target;
	cin >> n >> target;

	int a[100000] = { 0 };
	for (int i = 0; i < n; i++)
		cin >> a[i];

	int left = 0;
	int right = n - 1;

	int res[2] = {-1,-1};    //初值为-1，core不做改变的话，输出初值

	core(a, left, right, target, res, n);

	cout <<"["<< res[0] << "," << res[1]<<"]";    //注意输出格式是类似[3,4]

	return 0;
}

编辑于 2019-09-02 14:14:30 回复(0)

Python

永恒夜猫忍

啊啊啊啊，老通不过。。。求大神指导一下，为啥啊

n, target = map(int, input().strip().split())
array = list(map(int, input().strip().split()))
length = len (array)
if length == 0:
    print([-1,-1])
if array[0] <= target and array[-1] >= target:
    left, right = 0,length-1
while left <= right:
    mid = (left + right) // 2
    if array[mid] == target:
        right = left = mid
        while left-1 >= 0 and array[left-1] == target:
              left -= 1
        while right+1 <= length-1 and array[right+1] == target:
              right += 1
        print([left, right])
        break
    elif array[mid] < target:
          left = mid + 1
    else:
          right = mid - 1

发表于 2019-08-22 18:00:49 回复(0)

偷偷瞄一眼牛客

二分查找，只是二分查找找到目标后不马上结束，而是继续往左往右递归二分直到找不到为止

import java.util.*;

	publicclassMain{



	    publicstaticvoidmain(String[] args){



	        intn,target;



	        int[] result;



	        int[] num;



	        Scanner sc = newScanner(System.in);



	        while(sc.hasNext()){



	            n = sc.nextInt();



	            target = sc.nextInt();



	            result = newint[2];



	            result[0] = -1;



	            result[1] = -1;



	            num = newint[n];



	            for(inti = 0;i < n;i ++){



	                num[i] = sc.nextInt();



	            }



	            find(target,num,result,0,n - 1);



	            System.out.println("["+result[0] +","+result[1]+"]");



	        }



	    }



	    privatestaticvoidfind(inttarget,int[] a,int[] result,intleft,intright){



	        intmid;



	        while(left <= right){



	            mid = (left + right)/2;



	            if(a[mid] > target){



	                right = mid - 1;



	            }



	            elseif(a[mid] < target){



	                left = mid + 1;



	            }



	            else{



	                if(result[0] > -1&& result[1] > -1){



	                    if(mid < result[0])



	                        result[0] = mid;



	                    elseif(result[1] < mid)



	                        result[1] = mid;



	                }



	                else{



	                    result[0] = mid;



	                    result[1] = mid;



	                }



	                find(target,a,result,left,mid - 1); //在目标的左侧继续二分查找



	                find(target,a,result,mid + 1,right );//右侧找



	                break;



	            }



	        }



	    }



	}