Java/SearchRange.java at master · rjtsdl/Java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

public class SearchRange {
	    public int[] searchRange(int[] A, int target) {
	        // Start typing your Java solution below
	        // DO NOT write main() function

	        int[] pos = new int [2];
	        pos[1] = -1;
	        pos[0] = -1;
	        int start0 =0;
	        int end0 = A.length-1;
	        int start1 = 0;
	        int end1 = A.length -1;
	        int mid = start0 +(end0-start0)/2;
	        do{
	            if(A[mid]==target){
	                end0=mid;
	            }

	            else if(A[mid]< target){
	                start0 = mid+1;
	            }
	            else{
	                end0 = mid-1;
	                end1 = mid-1;
	            }

	            mid = start0+(end0-start0)/2;
	        }
	        while(start0<end0-1);

	        if(start0>A.length-1||end0<0) return pos;

	        if(A[start0] == target){
	            pos[0] = start0;
	        }
	        else if(A[end0] == target){
	            pos[0] = end0;
	        }
	        else{
	            pos[0] = -1;
	            pos[1] = -1;
	            return pos;
	        }

	        start1= pos[0];
	        mid = start1 + (end1-start1)/2;

	        do{
	            if(A[mid]==target){
	                start1=mid;
	            }
	            else if(A[mid]>target){
	                end1= mid-1;
	            }
	            mid = start1+(end1-start1)/2;
	        }
	        while(start1<end1-1);

	        if(A[end1] == target){
	            pos[1] = end1;
	        }else{
	            pos[1] = start1;
	        }

	        return pos;


	    }


}