LeetCode - Medium - 33. Search in Rotated Sorted Array

红太狼 2023-01-04 11:53 114阅读 0赞

## Topic ##

*  Array
 *  Binary Search

## Description ##

[https://leetcode.com/problems/search-in-rotated-sorted-array/][https_leetcode.com_problems_search-in-rotated-sorted-array]

You are given an integer array `nums` sorted in ascending order (with **distinct** values), and an integer `target`.

Suppose that `nums` is rotated at some pivot unknown to you beforehand (i.e., `[0,1,2,4,5,6,7]` might become `[4,5,6,7,0,1,2]`).

If `target` is found in the array return its index, otherwise, return `-1`.

**Example 1**:

Input: nums = [4,5,6,7,0,1,2], target = 0
    Output: 4

**Example 2**:

Input: nums = [4,5,6,7,0,1,2], target = 3
    Output: -1

**Example 3**:

Input: nums = [1], target = 0
    Output: -1

**Constraints**:

*  `1 <= nums.length <= 5000`
 *  `-10⁴ <= nums[i] <= 10⁴`
 *  All values of `nums` are **unique**.
 *  `nums` is guaranteed to be rotated at some pivot.
 *  `-10⁴ <= target <= 10⁴`

## Analysis ##

方法一：我写的，先用二分法找出原第一元素，然后以原第一元素将数组一分为二，根据target与边界值比较，决定在其中之一数组再用二分查找出target。

--------------------

方法二：The main idea is that we need to find some parts of array that we could adopt binary search on that, **which means we need to find some completed sorted parts**, then determine whether target is in left part or right part. There is at least one segment (left part or right part) is **continuously monotonously increasing**连续单调递增.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70]

*  If the entire left part is continuously monotonically increasing, which means the pivot point is on the right part
    
     *  If left <= target < mid ------> drop the right half
     *  Else ------> drop the left half
 *  If the entire right part is continuously monotonically increasing, which means the pivot point is on the left part
    
     *  If mid < target <= right ------> drop the left half
     *  Else ------> drop the right half

--------------------

方法三：

二分查找一次循环过程

target:0     nums:[4, 5, 6, 7, 0, 1, 2]
    
    left     mid        right
    |        |          |
    4, 5, 6, 7,   0, 1, 2
                  |
                  target
    
    After comparing nums[0]:4, target<4 and nums[mid]>4 are not on the same side.
    Temporily change nums[mid] to -INF.(target:0 < nums[0]:4 ? -INF : INF)
    
    left       mid         right
    |          |           |
    4, 5, 6, -INF,   0, 1, 2
                     |
                     target
    
    nums[mid]:-INF < target:0, left is changed to mid+1.
    
                    left=mid+1
               mid   |     right
               |     |     |
    4, 5, 6, -INF,   0, 1, 2
                     |
                     target
    
    finish 1 loop

修改成-INF或INF并不是真正修改数组元素，它只是暂时替换，它的目的主要是让二分查找能在这旋转数组做真正的二分查找。（结合代码理解这句话）

--------------------

方法四：首先，用二分查找找出最小元素值的下标`minValueIndex`，然后，得出用原递增数组下标与旋转后数组下标之间映射关系`RIndex = (OIndex + minValueIndex) % arrayLeagth`，这样就可正常用二分查找算法找出目标下标。

一个例子：
    
    Rotated Sorted Array(RSA)
    RSA:[3, 4, 5, 6, 7, 0, 1, 2]
    
    最小元素值为rsa[5]：0，minValueIndex：5
    
    ---
    
    Original Sorted Array(OSA)（这里故意让元素及其下标相等，方便理解）。
    OSA:[0, 1, 2, 3, 4, 5, 6, 7]
         |        |           |
         left     mid         right
    
    idx  0  1  2  3  4  5  6  7
    RSA:[3, 4, 5, 6, 7, 0, 1, 2]
    
    例如，OSA元素3（下标也为3）的对应在下标RSA的下标为：
    RIndex = (OIndex + minValueIndex) % arrayLeagth = (3 + 5) % 8 = 0

这样的话我们可以直接地用二分查找，间接找出target。

## Submission ##

public class SearchInRotatedSortedArray { 
    
    	// 方法一：
    	public int search1(int[] nums, int target) { 
    		// 找出原第一元素
    		int startIndex = searchStartIndex(nums);
    
    		if (nums[0] <= target && startIndex - 1 >= 0 && target <= nums[startIndex - 1]) { 
    			return binarySearch(nums, 0, startIndex - 1, target);
    		}
    
    		if (nums[startIndex] <= target && target <= nums[nums.length - 1]) { 
    			return binarySearch(nums, startIndex, nums.length - 1, target);
    		}
    		return -1;
    	}
    
    	private int binarySearch(int[] nums, int left, int right, int target) { 
    		while (left <= right) { 
    			int mid = left + (right - left) / 2;
    
    			if (target < nums[mid]) { 
    				right = mid - 1;
    			} else if (target > nums[mid]) { 
    				left = mid + 1;
    			} else { 
    				return mid;
    			}
    		}
    		return -1;
    	}
    
    	// 找出原第一元素
    	private int searchStartIndex(int[] nums) { 
    		int left = 0, right = nums.length - 1;
    		while (left <= right) { 
    			int mid = left + (right - left) / 2;
    			if (0 <= mid - 1 && nums[mid - 1] > nums[mid])
    				return mid;
    
    			if (mid + 1 <= nums.length - 1 && nums[mid] > nums[mid + 1])
    				return mid + 1;
    
    			if (nums[0] < nums[mid]) { 
    				left = mid + 1;
    			} else { 
    				right = mid - 1;
    			}
    		}
    		return 0;
    	}
    
    	// 方法二：
    	public int search2(int[] nums, int target) { 
    		if (nums == null || nums.length == 0) { 
    			return -1;
    		}
    
    		/* . */
    		int left = 0, right = nums.length - 1;
    		// when we use the condition "left <= right", we do not need to determine if
    		// nums[left] == target
    		// in outside of loop, because the jumping condition is left > right, we will
    		// have the determination
    		// condition if(target == nums[mid]) inside of loop
    		while (left <= right) { 
    			// left bias
    			int mid = left + (right - left) / 2;
    			if (target == nums[mid]) { 
    				return mid;
    			}
    			// if left part is continuously monotonically increasing, or the pivot point is
    			// on the right part
    			if (nums[left] <= nums[mid]) { 
    				// must use "<=" at here since we need to make sure target is in the left part,
    				// then safely drop the right part
    				if (nums[left] <= target && target < nums[mid]) { 
    					right = mid - 1;
    				} else { 
    					// right bias
    					left = mid + 1;
    				}
    			} // if right part is continuously monotonically increasing, or the pivot point is
    				// on the left part
    			else { 
    				// must use "<=" at here since we need to make sure target is in the right part,
    				// then safely drop the left part
    				if (nums[mid] < target && target <= nums[right]) { 
    					left = mid + 1;
    				} else { 
    					right = mid - 1;
    				}
    			}
    		}
    		return -1;
    	}
    
    	// 方法三：
    	public int search3(int[] nums, int target) { 
    		int left = 0, right = nums.length - 1;
    		while (left <= right) { 
    			int mid = left + (right - left) / 2;
    			int midNum = nums[mid];
    			// If nums[mid] and target are "on the same side" of nums[0], we just take
    			// nums[mid].
    			boolean midNumAndTargetOnTheSameSide = (nums[mid] > nums[0]) == (target > nums[0]);
    
    			if (!midNumAndTargetOnTheSameSide) { 
    				midNum = target < nums[0] ? Integer.MIN_VALUE : Integer.MAX_VALUE;
    			}
    
    			if (midNum < target)
    				left = mid + 1;
    			else if (midNum > target)
    				right = mid - 1;
    			else
    				return mid;
    		}
    		return -1;
    	}
    
    	// 方法四；
    	public int search4(int[] nums, int target) { 
    		int left = 0, right = nums.length - 1;
    		// find the index of the smallest value using binary search.
    		// Loop will terminate since mid < right, and left or right will shrink by at
    		// least 1.
    		// Proof by contradiction that mid < right: if mid==right, then left==right and
    		// loop would
    		// have been terminated.
    		while (left < right) { 
    			int mid = left + (right - left) / 2;
    			if (nums[mid] > nums[right])
    				left = mid + 1;
    			else
    				right = mid;
    		}
    		// left==right is the index of the smallest value and also the number of places
    		// rotated.
    		int rot = left;
    		left = 0;
    		right = nums.length - 1;
    		// The usual binary search and accounting for rotation.
    		while (left <= right) { 
    			int mid = left + (right - left) / 2;
    			int rotMid = (mid + rot) % nums.length;
    			if (nums[rotMid] == target)
    				return rotMid;
    			if (nums[rotMid] < target)
    				left = mid + 1;
    			else
    				right = mid - 1;
    		}
    		return -1;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    
    import java.lang.reflect.InvocationTargetException;
    import java.lang.reflect.Method;
    
    import org.junit.Test;
    
    public class SearchInRotatedSortedArrayTest { 
    
    	@Test
    	public void test1() { 
    		SearchInRotatedSortedArray obj = new SearchInRotatedSortedArray();
    
    		assertEquals(4, obj.search1(new int[] {  4, 5, 6, 7, 0, 1, 2 }, 0));
    		assertEquals(-1, obj.search1(new int[] {  4, 5, 6, 7, 0, 1, 2 }, 3));
    		assertEquals(-1, obj.search1(new int[] {  1 }, 0));
    	}
    
    	@Test
    	public void test2() { 
    		SearchInRotatedSortedArray obj = new SearchInRotatedSortedArray();
    
    		assertEquals(4, obj.search2(new int[] {  4, 5, 6, 7, 0, 1, 2 }, 0));
    		assertEquals(-1, obj.search2(new int[] {  4, 5, 6, 7, 0, 1, 2 }, 3));
    		assertEquals(-1, obj.search2(new int[] {  1 }, 0));
    	}
    
    	@Test
    	public void test3() { 
    		SearchInRotatedSortedArray obj = new SearchInRotatedSortedArray();
    
    		assertEquals(4, obj.search3(new int[] {  4, 5, 6, 7, 0, 1, 2 }, 0));
    		assertEquals(-1, obj.search3(new int[] {  4, 5, 6, 7, 0, 1, 2 }, 3));
    		assertEquals(-1, obj.search3(new int[] {  1 }, 0));
    	}
    
    	@Test
    	public void test4() { 
    		SearchInRotatedSortedArray obj = new SearchInRotatedSortedArray();
    
    		assertEquals(4, obj.search4(new int[] {  4, 5, 6, 7, 0, 1, 2 }, 0));
    		assertEquals(-1, obj.search4(new int[] {  4, 5, 6, 7, 0, 1, 2 }, 3));
    		assertEquals(-1, obj.search4(new int[] {  1 }, 0));
    	}
    
    	@Test
    	public void testSearchStartIndexMethod() throws NoSuchMethodException, SecurityException //
    			, IllegalAccessException, IllegalArgumentException, InvocationTargetException { 
    		SearchInRotatedSortedArray obj = new SearchInRotatedSortedArray();
    		Method searchStartIndexMethod = obj.getClass().getDeclaredMethod("searchStartIndex", int[].class);
    		searchStartIndexMethod.setAccessible(true);
    
    		assertEquals(4, searchStartIndexMethod.invoke(obj, new int[] {  4, 5, 6, 7, 0, 1, 2 }));
    		assertEquals(1, searchStartIndexMethod.invoke(obj, new int[] {  7, 0, 1, 2, 3, 4, 5, 6, }));
    		assertEquals(0, searchStartIndexMethod.invoke(obj, new int[] {  1 }));
    		assertEquals(0, searchStartIndexMethod.invoke(obj, new int[] {  1, 2 }));
    		assertEquals(1, searchStartIndexMethod.invoke(obj, new int[] {  2, 1 }));
    	}
    }

[https_leetcode.com_problems_search-in-rotated-sorted-array]: https://leetcode.com/problems/search-in-rotated-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70]: /images/20221119/7a26a2a82a564c5e8dc40ef3baa2e64e.png