Search in Rotated Sorted Array
给一个排序后被partial翻转的数组, 找一个元素. 利用排序, 做二叉搜索. 主要是要分类讨论.
|
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 class Solution { public int search(int[] nums, int target) { if(nums.length == 0 || nums == null) return 0; int l = 0; int r = nums.length - 1; while(l <=r) { int mid = l + (r - l) / 2; if(nums[mid] == target) return mid; else if(nums[mid] >= nums[l]){ if(nums[l]<=target && target < nums[mid]) r = mid - 1; else l = mid + 1; } else{ if(nums[mid] < target && target <= nums[r]) l = mid + 1; else r = mid - 1; } } return -1; } } |