leetcode4/SearchForARange.java at master · 1code/leetcode4 · 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
public class Solution {
    public int[] searchRange(int[] A, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int re[] = new int[2];

		re[0] = searchFirst(A,target);
		re[1] = searchLast(A,target);

		return re;
    }

	public int searchFirst(int[] A, int target){
		if(A.length==0) return -1;
		if(A.length==1) return (A[0] == target ? 0:-1);

		int i=0;
		int j=A.length-1;

		while(j>i){
			int m = (i+j)/2;
			if(A[m]>target)
				j = m-1;
			else if(A[m]<target)
				i = m+1;
			else
				j = m;
		}

		if(i==j){
			if(A[i] == target)
				return i;
			else
				return -1;
		}

		return -1;
	}

	public int searchLast(int[] A, int target){
		if(A.length==0) return -1;
		if(A.length==1) return (A[0] == target ? 0:-1);

		int i=0;
		int j=A.length-1;

		while(j>i){
			if(A[i] == target && j == i+1){
				if(A[j] == target)
					return j;
				else
					return i;
			}

			int m = (i+j)/2;
			if(A[m]>target)
				j = m-1;
			else if(A[m]<target)
				i = m+1;
			else
				i = m;
		}

		if(i==j){
			if(A[i] == target)
				return i;
			else
				return -1;
		}

		return -1;

	}
}