SHARE
TWEET

Untitled

a guest Mar 20th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. func search(nums []int, target int) int {
  2.     nL := len(nums)
  3.     if nL == 0 {
  4.         return -1
  5.     } else if nL == 1 {
  6.         if nums[0] == target {
  7.             return 0
  8.         } else {
  9.             return -1
  10.         }
  11.     }
  12.     p := findPivot(nums)
  13.     var l, r int
  14.     if p == -1 {
  15.         l = 0
  16.         r = nL - 1
  17.     } else {
  18.         if nums[0] > target {
  19.             l = p + 1
  20.             r = nL - 1
  21.         } else if nums[0] == target {
  22.             return 0
  23.         } else {
  24.             l = 1
  25.             r = p
  26.         }
  27.     }
  28.  
  29.     for mid := (l + r) / 2; l <= r; {
  30.         if nums[mid] == target {
  31.             return mid
  32.         }
  33.         if nums[mid] < target {
  34.             l = mid + 1
  35.         } else {
  36.             r = mid - 1
  37.         }
  38.         mid = (l + r) / 2
  39.     }
  40.     return -1
  41. }
  42.  
  43. // [4,5,6,7,0,1,2] -> index:3
  44. func findPivot(nums []int) int {
  45.     if len(nums) <= 1 {
  46.         return -1
  47.     }
  48.  
  49.     l, r := 0, len(nums)-1
  50.     i := r / 2
  51.     for l <= r {
  52.         if i >= len(nums)-1 {
  53.             break
  54.         }
  55.         if nums[i] <= nums[i+1] {
  56.             if nums[i] < nums[0] {
  57.                 // turn left
  58.                 r = i - 1
  59.             } else {
  60.                 // turn right
  61.                 l = i + 1
  62.             }
  63.             i = (l + r) / 2
  64.         } else {
  65.             return i
  66.         }
  67.  
  68.     }
  69.     return -1
  70. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top