leetcode/33_search_in_rotated_sorted_array

33_search_in_rotated_sorted_array

dz / leetcode / 33_search_in_rotated_sorted_array

Summary

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

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