Search for rotated ordered array

Question

Work on the algorithm below. Reporting a problem and resolving a problem. The question is, do we need to “look for both halves” to keep it safe? Or, when a[left] == a[mid] , we can simply search for the right side without checking if a[mid] == a[right] - because when a[left] == a[mid] , I think that all elements on the left are equal and cannot be satisfied with the search condition in order to find the value.

In more detail, I mean, is it safe to write the latter if as,

 else if (a[left] == a[mid]) { return search(a, mid + 1, right, x); } 

Description of the problem

Given a sorted array of n integers that were rotated an unknown number of times, write code to find the element in the array, you can assume that the array was originally sorted in ascending order

Example, Input search 5 in {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14} Output, 8 (index 5 in the array)

code

 public static int search(int a[], int left, int right, int x) { int mid = (left + right) / 2; if (x == a[mid]) { // Found element return mid; } if (right < left) { return -1; } /* While there may be an inflection point due to the rotation, either the left or * right half must be normally ordered. We can look at the normally ordered half * to make a determination as to which half we should search. */ if (a[left] < a[mid]) { // Left is normally ordered. if (x >= a[left] && x < a[mid]) { return search(a, left, mid - 1, x); } else { return search(a, mid + 1, right, x); } } else if (a[mid] < a[left]) { // Right is normally ordered. if (x > a[mid] && x <= a[right]) { return search(a, mid + 1, right, x); } else { return search(a, left, mid - 1, x); } } else if (a[left] == a[mid]) { // Left is either all repeats OR loops around (with the right half being all dups) if (a[mid] != a[right]) { // If right half is different, search there return search(a, mid + 1, right, x); } else { // Else, we have to search both halves int result = search(a, left, mid - 1, x); if (result == -1) { return search(a, mid + 1, right, x); } else { return result; } } } return -1; } 

Answer 1

As for your question, your assumption is perfectly correct that you do not need to look for both halves. You can simply search for the right half, since if a[mid] != key , your element will undoubtedly be in the right half if it is in an array.

EDIT:

The above conclusion is incomplete. Now I will write a new one, with further reflection.

Firstly, if you are looking for both halves at any given time, it makes no sense to do a binary search, since the complexity of your search becomes O(n) .

Now you are right there, that if a[mid] == a[left] , your key can be in any of the halves. But, on the one hand, you can be sure that one of the halves will have all elements equal.

 eg. Suppose a[12] = [1,1,1,2,2,2,2,2,2,2,2,2] rotate r=2 times, a`[12] = [2,2,1,1,1,2,2,2,2,2,2,2] so, a[mid] = a[left] = 2 if key = 1, it is in left half. now, rotate r=9 times, a``[12] = [2,2,2,2,2,2,2,2,2,1,1,1] so, a[mid] = a[left] = 2 if key = 1, it is in right half 

So, you need to search both halves of this array for your key, and this case actually makes the binary search redundant.

So, now I even suggest you use the solution mentioned below.

Although, if there are no restrictions, I would like to offer him a solution:

This is a simple variation of the Binary Search algorithm.

First you need to apply a binary search in an array with a termination condition:

 a[mid-1] > a[mid] 

Once this condition is met, you have the index k = mid , which gives you 2 sorted arrays.

The first array, A[0...k-1] and the second array, A[k...n-1] , assuming n elements.

Now just check.

 if(key > A[0]) Binary Search in A[0...k-1] else Binary Search in A[k...n-1] 

One exception, if the array was rotated n times, you will not get the value k . Binary search of the entire array for a key.

EDIT2: Answering your questions from the comments

I am interested in my original method if [left] <a [mid] and x> = a [left] && x <a [mid], if it is safe to search only on the left side using search (a, left, mid-1, x); if the array can be rotated n times?

If a[left] < a[mid] , then we can be sure that a[left...mid] increases in order (sorted). So, if x >= a[left] && x < a[mid] , searching only in the left half is enough.

if you can also specify when [left] == ​​a [mid] and [mid] == a [right], do we need to search in both directions?

Yes. In this case, we need to look for both directions. Say for example. your original array is {1,2,2,2,2,2,2,2,2,2} that rotates once. The array becomes, {2,1,2,2,2,2,2,2,2,2} . If he turns 8 times, he becomes {2,2,2,2,2,2,2,2,1,2} . Now, if your search key is 1 , right at the beginning, in both cases, a[mid] == a[left] == a[right] , and your key is in different halves. So you need to look for both halves for the key.

Answer 2

There are two things you need to consider.

At first, when the array rotates, it means that it looks like a circular buffer, so you need to access the array differently to avoid going from the border of the array.

 Normal array[index] Circular array[index % size] 

Secondly, you need to consider rotation, the first ordered element is not index 0 , let's say it is index f as the first, so to access the ordered index i you use i+f .

 Normal array[index] Circular array[index % size] Rotated array[(index + first) % size] 

To find the first element of a rotated ordered array, we can check where the sort condition is violated.

 // assuming ascending order a[0] <= a[1] int find_first_index (int [] arr) { for(int i = 0; i < arr.length; i++) { if(arr[i] > arr[(i+1) % arr.length]) { return (i+1) % arr.length; } } return 0; } 

Now you just need to get this first index before sorting.

 int f = find_first_index(arr); 

Then replace all array access in the sorting algorithm [(i+f) % arr.length] with arr[i] . This way your code will become like this.

 public static int startSearch(int a[], int x) { int f = find_first_index(a); return search(a, f, 0, (a.length-1), x); } public static int search(int a[], int f, int left, int right, int x) { int s = a.length; int mid = (left + right) / 2; if (x == a[(mid+f)%s]) { // Found element return mid; } if (right < left) { return -1; } .. 

.. full source code here