[JAVA] Algorithm gymnastics 3

Search Rotated Array A sorted array that has been rotated to the right by an arbitrary number and the specified number (key) are passed and searched.

Description

Finds the specified number (key) in a sorted array that has been rotated by any number. Returns -1 if the Key does not exist. Suppose the array contains no duplicates. Below is the original array before rotation. Screen Shot 2019-12-17 at 15.15.54.png If you rotate this array 6 times, it will change as follows. Screen Shot 2019-12-17 at 15.18.04.png

conditions

  1. Linear search O (n) is an unacceptable solution.
  2. Consider a modified Binary Search.

Solution Runtime Complexity O(logn) I am using Binary Search. Memory Complexity O(logn). For each loop, the passed Array is cut in half and only one is searched.

Commentary

The solution is basically a Binary Search, but with some fixes. If you look closely at the example array, you can see that at least half of the array is always sorted. Take advantage of this feature. If the number n you are looking for is in the sorted half of the array, you can find it with a Binary Search. Otherwise, discard the sorted halves and continue examining the unsorted halves. This splits the array in half at each step, which makes the Runtime Complexity O (logn). There are some conditional parts in the code that are a little hard to read. Under four conditions

  1. When the SubArray in the range of start ~ mid cut in half is sorted ** and the Key you are looking for exists in that range.
  2. When the SubArray in the range of mid to end cut in half is sorted ** and the Key you are looking for exists in that range.
  3. When the SubArray in the range of start ~ mid cut in half is not sorted ** and the Key you are looking for exists in that range.
  4. When the SubArray in the mid to end range cut in half is not ** sorted ** and the Key you are looking for exists in that range. The conditions are divided as such.

Implementation

Screen Shot 2019-12-17 at 16.05.32.png

test

Screen Shot 2019-12-17 at 16.07.05.png

Output

Screen Shot 2019-12-17 at 16.09.54.png

Recommended Posts

Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm exercise 6
Algorithm Gymnastics 24 Reverse a Linked List
Python algorithm
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm