[LeetCode][81. Search in Rotated Sorted Array II] The Key of Binary Search Is Narrow the Search Interval

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 2 分钟

By Long Luo

This article is the solution of Problem 81. Search in Rotated Sorted Array II.

Brute Force

The Brute Force solution is so easy.

Problem 33. Search in Rotated Sorted Array.

1
2
3
4
5
6
7
8
9
10
public static int search_bf(int[] nums, int target) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (nums[i] == target) {
            return i;
        }
    }

    return -1;
}

Problem 81. Search in Rotated Sorted Array II:

1
2
3
4
5
6
7
8
9
10
public static boolean search_bf(int[] nums, int target) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (nums[i] == target) {
            return true;
        }
    }

    return false;
}

Analysis

  • Time Complexity: \(O(n)\).
  • Space Complexity: \(O(1)\).

Binary Search

Step-by-step Binary Search Algorithm:

We basically ignore half of the elements just after one comparison.

  1. Compare target with the middle element;
  2. If target matches with the middle element, we return the mid index;
  3. Else If target is greater than the mid element, then target can only lie in the right half subarray after the mid element. So we recursive for the right half;
  4. Else (target is smaller) recursive for the left half.

The Key of Binary Search is Narrow the Search Interval, aka reducing the scale of the problem.

Every round exclusive the interval where the target element must not exist, so the scale of the problem is gradually reduced.

Problem 33. Search in Rotated Sorted Array.

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
 public static int search_binary_2(int[] nums, int target) {
     int len = nums.length;
     int left = 0;
     int right = len - 1;
     while (left < right) {
// right - left + 1 just in case the dead loop, for we set the right margin is mid - 1.
// num / 2 is floor.
         int mid = left + (right - left + 1) / 2;
         if (nums[mid] < nums[right]) {
             if (target >= nums[left] && target <= nums[right]) {
                 left = mid;
             } else {
                 right = mid - 1;
             }
         } else if (nums[mid] >= nums[right]) {
             if (target >= nums[left] && target <= nums[mid - 1]) {
                 right = mid - 1;
             } else {
                 left = mid;
             }
         }
     }

     if (nums[left] == target) {
         return left;
     }

     return -1;
 }

Problem 81. Search in Rotated Sorted Array II:

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
public static boolean search_binary(int[] nums, int target) {
    int len = nums.length;
    int left = 0;
    int right = len - 1;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (nums[mid] < nums[right]) {
            if (nums[mid] <= target && target <= nums[right]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        } else if (nums[mid] > nums[right]) {
            if (nums[left] <= target && nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        } else if (nums[mid] == nums[right]) {
            if (nums[mid] == target) {
                return true;
            }
            right = right - 1;
        }
    }

    return nums[right] == target;
}

Analysis

  • Time Complexity: \(O(nlogn)\).
  • Space Complexity: \(O(1)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗