面试题 10.03. 搜索旋转数组

中点值与左侧端点比较

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
class Solution {
    public int search(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            if (arr[left] == target) {
                // 如果最左侧是目标值则直接返回
                return left;
            }

            int mid = (left + right) >>> 1;
            if (arr[mid] == target) {
                // 中点是目标值，缩小区间
                right = mid; // 此处不会导致死循环是因为当单个元素是目标值时上方会直接返回
            } else {
                // arr[mid] != target
                if (arr[left] < arr[mid]) {
                    // 左侧数组递增
                    if (arr[left] <= target && target < arr[mid]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                } else if (arr[left] > arr[mid]) {
                    // 右侧数组递增
                    if (arr[mid] < target && target <= arr[right]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                } else {
                    // arr[left] == arr[mid] && arr[left] != target
                    left++;
                }
            }
        }

        return -1;
    }
}

中点值与右侧端点比较

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
class Solution {
    public int search(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            if (arr[left] == target) {
                // 如果最左侧是目标值则直接返回
                return left;
            }

            int mid = (left + right) >>> 1;
            if (arr[mid] == target) {
                // 中点是目标值，缩小区间
                right = mid; // 此处不会导致死循环是因为当单个元素是目标值时上方会直接返回
            } else {
                // arr[mid] != target
                if (arr[mid] < arr[right]) {
                    // 右侧数组递增
                    if (arr[mid] < target && target <= arr[right]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                } else if (arr[mid] > arr[right]) {
                    // 左侧数组递增
                    if (arr[left] < target && target < arr[mid]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                } else {
                    // arr[right] == arr[mid] && arr[right] != target
                    right--;
                }
            }
        }

        return -1;
    }
}

关键点在于最左侧是目标值时直接返回，否则 arr = [5, 5, 5, 1, 2, 3, 4, 5]，target = 5 不能 AC。

References

面试题 10.03. 搜索旋转数组