Last active
August 29, 2015 14:07
-
-
Save HDegano/ca7eddc62414fe0b0477 to your computer and use it in GitHub Desktop.
Find element in a rotated sorted Array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| Assumes no duplicate | |
| O(logN) | |
| */ | |
| public int FindElementInRotatedSortedArray(int[] ar, int k){ | |
| int n = ar.Length; | |
| int lo = 0; | |
| int hi = n - 1; | |
| while(lo <= hi){ | |
| int mid = lo + (hi - lo)/ 2; //prevent int overflow, assumes all positives | |
| if(ar[mid] == k) return mid; //found it, boom! | |
| //Ok we need to figure out what part is the sorted array and go from there | |
| if(ar[mid] <= ar[hi]){ //right side is sorted | |
| if(ar[mid] < k && k <= ar[hi]) | |
| lo = mid + 1; | |
| else | |
| hi = mid - 1; | |
| } | |
| else{ //left side is sorted | |
| if(ar[lo] <= k && k < ar[mid]) | |
| hi = mid -1; | |
| else | |
| lo = mid + 1; | |
| } | |
| } | |
| return -1; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Quick check if mid == k | |
| Figure out what side is sorted. We can use this to give us confidence and check if k is in the range of that sorted array. Update lo and hi appropriately |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment