33_search_in_rotated_sorted_array
dz / leetcode / 33_search_in_rotated_sorted_arraySummary
There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity.
Node Tree
- URL
- approach_1_binary_search
- binary_search_in_chosen_array
- choosing_based_on_rotation
- editorial
- find_rotation_index
- intuition
Nodes
URL | |
content | URL |
hyperlink | https://leetcode.com/problems/search-in-rotated-sorted-array |
intuition | |
content | Because they specify O(log(n)) performance, this is a divide an conquer problem. The added bit is the rotational bit. |
children | no_rotation, divide_and_conquer_binary_search (I initially thought "divide and conquer", it was "binary search") |
no_rotation | |
content | First, checking a set where there's no rotation. Given an array a numbers (starting with the full array), split the array into two arrays. The number, if it exists, will be in exactly one of these arrays (all numbers unique). Since they are sorted, this is a range check. Pick one of the ranges, and repeat the process until there is only one element left and the element is/isn't found. |
children | factoring_in_rotation (can this be modified to factor in pivot?) |
parents | intuition |
factoring_in_rotation | |
content | A rotation will introduce some kind of discontinuity in the array of sorted values. It would be trivial to have a linear sweep to find the pivot, but this problem doesn't want that. |
children | detecting_rotation |
parents | no_rotation |
detecting_rotation | |
content | In an unrotated array or subarray, the start/end values will be start < end. If a rotation happens, start > end. ex: 456 7012. |
children | pivot_check (I was thinking about pivots a little bit trying to detect,rotation in a binary search, but didn't get it quite right.) |
parents | factoring_in_rotation |
choosing_based_on_rotation | |
content | how do you choose which region to go on based on if there's rotation? It's a range check, but with extra logic. |
editorial | |
content | editorial |
approach_1_binary_search | |
content | Approach 1: Binary Search |
children | approach_2_one_pass_binary_search (revised binary search to do a single pass) |
find_rotation_index | |
content | Find =rotation index=, the smallest element in array (can be done via binary search). |
children | split_array_via_rotation_index (next) |
split_array_via_rotation_index | |
content | Split array via rotation index. |
children | identify_which_array_to_find_target (next) |
parents | find_rotation_index |
identify_which_array_to_find_target | |
content | Figure out which array has target by comparing nums[0] and target. |
parents | split_array_via_rotation_index |
binary_search_in_chosen_array | |
content | binary search in chosen array |
remarks | This time to look for the target I think? |
approach_2_one_pass_binary_search | |
content | Approach 2: one-pass binary search |
children | two_pointers |
parents | approach_1_binary_search |
two_pointers | |
content | two pointer, start/end to track the search scope |
children | move_pointer_to_mid_of_prev_search, check_if_mid_is_target |
parents | approach_2_one_pass_binary_search |
check_if_mid_is_target | |
content | check if mid is target |
parents | two_pointers |
move_pointer_to_mid_of_prev_search | |
content | At each iteration, reduce scope in half by moving the start/end pointer to the middle of the previous search. |
parents | two_pointers |
pivot_check | |
content | The pivot point (mid) has two checks: pivot element is larger than first element in first array, or it is smaller than first element in first array. |
children | pivot_larger_than_first_elem, pivot_smaller_than_first_elem, check_non_rotated_subarray |
parents | detecting_rotation |
pivot_larger_than_first_elem | |
content | If the pivot is larger than the first elem in the first subarray, first array (left) is non-rotated. |
children | pivot_smaller_than_first_elem (related), check_non_rotated_subarray (left is rotated subarray) |
parents | pivot_check |
pivot_smaller_than_first_elem | |
content | If pivot is smaller than first elem in first array, first array (left) is rotated. |
children | check_non_rotated_subarray (right is non-rotated subarray) |
parents | pivot_check, pivot_larger_than_first_elem |
check_non_rotated_subarray | |
content | Check if element is in non-rotated subarray. If it is, move in that direction, otherwise in opposite direction. |
children | at_most_one_rotated_subarray |
parents | pivot_smaller_than_first_elem, pivot_check, pivot_larger_than_first_elem |
at_most_one_rotated_subarray | |
content | I think I can deduce that there's always going to be at most one rotated subarray, meaning if you find a rotated subarray, the other subarray is guaranteed to be non-rotated. You can also have a situation where there are no rotated subarrays, in which case the algorithm will still work. |
parents | check_non_rotated_subarray |
divide_and_conquer_binary_search | |
content | Observation: a lot of what I've been calling "divide and conquer" ends up being more specifically "binary search". I think I need to spend some time studying binary search. |
children | wikipedia_binary_search |
parents | intuition |
wikipedia_binary_search | |
content | Wikipedia page on binary search |
parents | divide_and_conquer_binary_search |
remarks | I've run into enough problems that boil down to binary search that I think it's worth reading about this. |
hyperlink | https://en.wikipedia.org/wiki/Binary_search_algorithm |