java算法之Search for a Range

最新推荐文章于 2024-05-19 23:17:06 发布

NFMSR

最新推荐文章于 2024-05-19 23:17:06 发布

阅读量536

点赞数

分类专栏：算法文章标签： java 二分查找遍历 rangeSearch

本文链接：https://blog.csdn.net/NFMSR/article/details/78383803

版权

算法专栏收录该内容

20 篇文章

订阅专栏

问题：Search for a Range

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

思路：因为题目要求用 O(log n)时间复杂度，所以我们考虑用二分查找方法，我们只需要找到一个target的位置，

然后指定两个指针，分别从target位置依次向前向后遍历，找到所有的target值就好。。题目不难

代码：

import java.util.Arrays;

public class SearchOfRange {

	public static void main(String[] args) {
		int[] a=new int[] {8,8,8,8,8,10};
		int target=8;
		int []result=searchRange(a, target);
		System.out.println(Arrays.toString(result));
		
	}
	public static int[] searchRange(int []a, int target) {
		int end=a.length;
		int start=0;
		int mid=0;
		while(start<end) {
			 mid=(end+start)/2;
			if(a[mid]<target) {	
				end=mid-1;
			}
			if(a[mid]>target) {
				start=mid+1;
			}else break;
				
		}
		
		int []result=new int[2];
		
		if(a[mid]==target) {
			int rangeStart=mid;
			int rangeEnd=mid;
			//这里rangStart不能等于0,如果等于0的话，rangeStart-1则为-1
			while(rangeStart>0&&a[rangeStart-1]==target) rangeStart--;
			while(rangeEnd<a.length-1&&a[rangeEnd+1]==target) rangeEnd++;
			result[0]=rangeStart;
			result[1]=rangeEnd;
		}else {
			result[0]=-1;
			result[1]=-1;
		}
		
		return result;
	}
}