Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Searching for an element in a circular sorted array

We want to search for a given element in a circular sorted array in complexity not greater than O(log n).
Example: Search for 13 in {5,9,13,1,3}.

My idea was to convert the circular array into a regular sorted array then do a binary search on the resulting array, but my problem was the algorithm I came up was stupid that it takes O(n) in the worst case:

for(i = 1; i < a.length; i++){     if (a[i] < a[i-1]){         minIndex = i; break;     } } 

then the corresponding index of ith element will be determined from the following relation:

(i + minInex - 1) % a.length 

it is clear that my conversion (from circular to regular) algorithm may take O(n), so we need a better one.

According to ire_and_curses idea, here is the solution in Java:

public int circularArraySearch(int[] a, int low, int high, int x){     //instead of using the division op. (which surprisingly fails on big numbers)     //we will use the unsigned right shift to get the average     int mid = (low + high) >>> 1;     if(a[mid] == x){         return mid;     }     //a variable to indicate which half is sorted     //1 for left, 2 for right     int sortedHalf = 0;     if(a[low] <= a[mid]){         //the left half is sorted         sortedHalf = 1;         if(x <= a[mid] && x >= a[low]){             //the element is in this half             return binarySearch(a, low, mid, x);         }     }     if(a[mid] <= a[high]){         //the right half is sorted         sortedHalf = 2;         if(x >= a[mid] && x<= a[high] ){             return binarySearch(a, mid, high, x);         }     }     // repeat the process on the unsorted half     if(sortedHalf == 1){         //left is sorted, repeat the process on the right one         return circularArraySearch(a, mid, high, x);     }else{         //right is sorted, repeat the process on the left         return circularArraySearch(a, low, mid, x);     } } 

Hopefully this will work.

like image 688
guirgis Avatar asked May 14 '10 13:05

guirgis


People also ask

How do you search a target value in a rotated array Javascript?

var search = function(nums, target) { if(nums. length == 0 || nums == null) return -1; let left = 0; let right = nums. length-1; while(left < right){ let mid = Math. floor((left+right)/2); if(nums[mid]>nums[right]){ left = mid+1; }else{ right = mid; } } let pivot = left; left = 0; right = nums.

Does binary search work on rotated array?

You can use binary search on the rotated array (with some modifications). Let N be the number you are searching for: Read the first number (arr[start]) and the number in the middle of the array (arr[end]):


1 Answers

You can do this by taking advantage of the fact that the array is sorted, except for the special case of the pivot value and one of its neighbours.

  • Find the middle value of the array a.
  • If a[0] < a[mid], then all values in the first half of the array are sorted.
  • If a[mid] < a[last], then all values in the second half of the array are sorted.
  • Take the sorted half, and check whether your value lies within it (compare to the maximum idx in that half).
  • If so, just binary search that half.
  • If it doesn't, it must be in the unsorted half. Take that half and repeat this process, determining which half of that half is sorted, etc.
like image 164
ire_and_curses Avatar answered Oct 08 '22 20:10

ire_and_curses