package leetcode;

/**
 * https://leetcode.com/problems/search-in-rotated-sorted-array/
 */
public class Problem33 {
    public int search(int[] nums, int target) {
        int prev = 0;
        int current;
        for (current = 1; current < nums.length; current++) {
            if (nums[current] < nums[prev]) {
                break;
            }
            prev = current;
        }
        int startIdx = current;
        if (current == nums.length) {
            startIdx = 0;
        }
        return binarySearch(nums, target, 0, nums.length - 1, startIdx);
    }

    private int binarySearch(int[] nums, int target, int lo, int hi, int startIdx) {
        if (lo > hi) {
            return -1;
        }
        int mid = (lo + hi) / 2;
        int midIdx = startIdx + mid;
        if (midIdx >= nums.length) {
            midIdx = midIdx - nums.length;
        }
        if (nums[midIdx] == target) {
            return midIdx;
        }
        if (nums[midIdx] > target) {
            return binarySearch(nums, target, lo, mid - 1, startIdx);
        }
        return binarySearch(nums, target, mid + 1, hi, startIdx);
    }
}

@@ -171,20 +171,63 @@
    i
-nt prev = 0;
+f (nums.length == 0) %7B%0A            return -1;%0A        %7D
 %0A   
@@ -235,23 +235,23 @@
     int 
-current
+idx = 0
 ;%0A      
@@ -261,28 +261,20 @@
 or (
-current = 1; current
+int i = 0; i
  %3C n
@@ -287,17 +287,15 @@
 ngth
-; current
+ - 1; i
 ++) 
@@ -321,28 +321,23 @@
 ums%5B
-current%5D %3C
+i%5D %3E
  nums%5B
-prev
+i + 1
 %5D) %7B
@@ -357,55 +357,19 @@
     
-break;%0A            %7D%0A            prev = current
+idx = i + 1
 ;%0A  
@@ -370,34 +370,32 @@
  1;%0A        
-%7D%0A
         
 int startIdx
@@ -386,95 +386,28 @@
     
-int startIdx = current;%0A        if (current == nums.length) %7B%0A            startIdx = 0;
+break;%0A            %7D
 %0A   
@@ -454,16 +454,21 @@
  target,
+ idx,
  0, nums
@@ -474,30 +474,16 @@
 s.length
- - 1, startIdx
 );%0A    %7D
@@ -496,16 +496,23 @@
 private 
+static 
 int bina
@@ -552,32 +552,25 @@
 int 
-lo
+idx
 , int 
-h
 i, int 
-startIdx
+j
 ) %7B%0A
@@ -582,55 +582,80 @@
    i
-f (lo %3E hi) %7B%0A            return -1;%0A        %7D%0A
+nt left = i;%0A        int right = j;%0A        while (left %3C= right) %7B%0A    
     
@@ -674,14 +674,19 @@
 = (l
-o + hi
+eft + right
 ) / 
@@ -700,70 +700,94 @@
     
+    
 int mid
-Idx = startIdx
+Value = nums%5B(mid
  + 
-m
 id
-;%0A        if (midIdx %3E= nums.length
+x) %25 nums.length%5D;%0A            if (midValue == target
 ) %7B%0A
@@ -802,25 +802,32 @@
     
-midIdx = midIdx -
+    return (mid + idx) %25
  num
@@ -847,38 +847,34 @@
     
- %7D%0A
      
-   if (nums%5BmidIdx%5D ==
+%7D else if (midValue %3C
  tar
@@ -896,21 +896,26 @@
     
-return midIdx
+    left = mid + 1
 ;%0A  
@@ -924,46 +924,42 @@
     
-%7D%0A
     
-    if (nums%5BmidIdx%5D
+%7D else %7B // midValue
  %3E
+=
  target
-) %7B
 %0A   
@@ -971,74 +971,39 @@
     
-return binarySearch(nums, target, lo, mid - 1, startIdx);%0A
+    right = mid - 1;%0A  
         
 %7D%0A  
@@ -990,32 +990,34 @@
  - 1;%0A          
+  
 %7D%0A        return
@@ -1014,64 +1014,27 @@
     
-return binarySearch(nums, target, mid + 1, hi, startIdx)
+%7D%0A        return -1
 ;%0A  

Update problem 33