输入数据包括两行:
第一行两个整数n(1 ≤ n ≤ 10 ^ 5),和需要查找的数target
第二行n个整数,范围均在32位整数内,以空格分隔
输出格式为[begin,end],如果不存在就输出[-1,-1]
6 8 5 7 7 8 8 10
3 4
#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); } }
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的最小数(下界),注意最后还要检查是否存在
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) + ']')
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)+']')
//使用改进的二分查找:找到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; } } }
#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; }
这是一种不考虑时间复杂度的解法,将数组转化为字符串,再使用字符串的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 + "]"); } }
#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; }
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
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;}}}}