Friday, January 29, 2016

Searching an Element in a Rotated Sorted Array

Problem:

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently? You may assume no duplicate exists in the array.
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int search(int[] nums, int target) { int len = nums.length; int left=0, right=len-1; // find rotation lenght i.e. index of smallest number in the sort array while(left < right) { int mid = (left+right)/2; if(nums[mid] > nums[right]) { left = mid+1; } else { right = mid; } } // rotation lenght is same as index of left int rot = left; // do regular binary search with make use of rotation length left=0; right=len-1; while(left<=right) { int mid = (left+right)/2; int realMid = (rot+mid)%len; if(nums[realMid]==target) { return realMid; } else if(nums[realMid]<target) { left = mid+1; } else { right = mid-1; } } return -1; }
Click here for more Programming Interview Questions



No comments:

Post a Comment