Search in Rotated Sorted Array

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).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Solution:
1. public class Solution {
2. public int search(int[] nums, int target) {
3. int n = nums.length;
4. 5. return search(nums, 0, n - 1, target);
6. }
7. 8. int search(int[] nums, int lo, int hi, int target) {
9. if (lo > hi)
10. return -1;
11. 12. int mid = lo + (hi - lo) / 2;
13. 14. if (nums[mid] == target) {
15. return mid;
16. }
17. 18. if (nums[lo] <= nums[mid]) {
19. if (nums[lo] <= target && target < nums[mid]) {
20. return search(nums, lo, mid - 1, target);
21. } else {
22. return search(nums, mid + 1, hi, target);
23. }
24. } else {
25. if (nums[mid] < target && target <= nums[hi]) {
26. return search(nums, mid + 1, hi, target);
27. } else {
28. return search(nums, lo, mid - 1, target);
29. }
30. }
31. }
32. }