Leetcode-4/src/main/java/com/fishercoder/solutions/_81.java at master · codingwhite/Leetcode-4 · 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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
package com.fishercoder.solutions;

/**
 * Follow up for "Search in Rotated Sorted Array":
 What if duplicates are allowed?

 Would this affect the run-time complexity? How and why?

 Write a function to determine if a given target is in the array.
 */
public class _81 {

    public boolean search(int[] A, int target) {
        int len = A.length;
        if (len == 0) {
            return false;
        }
        if (len == 1) {
            if (A[0] == target) {
                return true;
            } else {
                return false;
            }
        }
        int watershed = A[0];
        int watershedIndex = 0;
        for (int i = 0; i < len - 1; i++) {
            if (A[i] > A[i + 1]) {
                watershed = A[i];
                watershedIndex = i;
                System.out.println("Place 1: watershed = " + watershed
                        + "\twatershedIndex = " + watershedIndex);
                for (int j = i + 1; j < len; j++) {
                    if (A[j] == A[i]) {
                        watershed = A[j];
                        watershedIndex = j;
                        System.out.println("Place 2: watershed = " + watershed
                                + "\twatershedIndex = " + watershedIndex);
                    } else {
                        break;
                    }
                }
            }
        }
        System.out.println("watershed = " + watershed + "\twatershedIndex = "
                + watershedIndex);
        if (target == watershed) {
            return true;
        } else if (target > watershed) {
			/*
			 * here is the tricky part: when target is greater than watershed,
			 * it's also possible that this list is ZERO rotated, i.e. it didn't
			 * rotate at all! Then at this moment, watershed is not the largest
			 * element int this array, so we need to binary search this whole
			 * array.
			 */
            if (watershedIndex == 0) {
                int start = 0;
                int end = len - 1;
                int mid = (start + end) / 2;
                while (start <= end) {
                    if (target > A[mid]) {
                        start = mid + 1;
                        mid = (start + end) / 2;
                    } else if (target < A[mid]) {
                        end = mid - 1;
                        mid = (start + end) / 2;
                    } else if (target == A[mid]) {
                        return true;
                    }
                }
                return false;
            } else {
                return false;
            }
        } else if (target < watershed) {
			/*
			 * target could be in either part of this sorted array, then we
			 * check if target is greater than A[0], if so, then search in the
			 * first part, if not, then check if it is greater than A[len - 1],
			 * if so, return -1, if not, search in the second part
			 */

            if (target == A[0]) {
                return true;
            } else if (target > A[0]) {
                int start = 1;
                int end = watershedIndex - 1;
                int mid = (start + end) / 2;
                while (start <= end) {
                    if (target > A[mid]) {
                        start = mid + 1;
                        mid = (start + end) / 2;
                    } else if (target < A[mid]) {
                        end = mid - 1;
                        mid = (start + end) / 2;
                    } else if (target == A[mid]) {
                        return true;
                    }
                }
                return false;
            } else if (target < A[0]) {
                if (target == A[len - 1]) {
                    return true;
                } else if (target > A[len - 1]) {
                    return false;
                } else if (target < A[len - 1]) {
                    int start = watershedIndex + 1;
                    int end = len - 2;
                    int mid = (start + end) / 2;
                    while (start <= end) {
                        if (target > A[mid]) {
                            start = mid + 1;
                            mid = (start + end) / 2;
                        } else if (target < A[mid]) {
                            end = mid - 1;
                            mid = (start + end) / 2;
                        } else if (target == A[mid]) {
                            return true;
                        }
                    }
                    return false;
                }
            }
        }
        return false;
    }

}