[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. If you rotate this array 6 times, it will change as follows.

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

test

Output