首页 > 代码库 > Leetcode Search for a Range
Leetcode Search for a Range
Given a sorted array of integers, 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].
这道题类似上一道题，但是这道题多出了一个可能存在重复的条件，
对于这道题的解题思路为：首先用二分查找找出要找的元素所在的位置，然后向前或向后查找所有的要找的元素
1 package Search.fora.Range; 2 3 public class SearchforaRange { 4 5 /** 6 * @param args 7 */ 8 public static void main(String[] args) { 9 // TODO Auto-generated method stub10 // int[] A={5, 7, 7, 8, 8, 10};11 int[] A={1,2,3};12 SearchforaRange service=new SearchforaRange();13 //int [] result=service.searchRange(A, 8);14 int [] result=service.searchRange(A, 1);15 System.out.println(result[0]);16 System.out.println(result[1]);17 }18 public int[] searchRange(int[] A, int target) {19 int [] result=new int[2];20 int len=A.length;21 int low=0;22 int hi=len-1;23 while(low<=hi){24 int mid=(low+hi)/2;25 if(A[mid]==target){26 //往后找点27 int j=mid+1;28 int i=mid-1;29 while(j<len&&A[j]==A[mid]){30 j++;31 }32 j=j-1;33 while(i>=0&&A[i]==A[mid]){34 i--;35 }36 i++;37 result[0]=i;38 result[1]=j;39 return result;40 }41 if(A[mid]<A[low]){42 if(target>A[mid]&&target<=A[hi]){43 low=mid+1;44 }else{45 hi=mid-1;46 }47 }else{48 if(A[low]<=target&&target<A[mid]){49 hi=mid-1;50 }else{51 low=mid+1;52 }53 }54 }55 result[0]=-1;56 result[1]=-1;57 return result;58 }59 }
Leetcode Search for a Range
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。