find_minimum_in_rotated_sorted_array

hitzzc · hitzzc · commit 58f23c36cf09 · 2016-10-14T17:20:13.000+08:00
diff --git a/README.md b/README.md
@@ -136,6 +136,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [150. evaluate reverse polish notation](https://github.com/hitzzc/go-leetcode/tree/master/evaluate_reverse_polish_notation)
 #### [151. reverse words in a string](https://github.com/hitzzc/go-leetcode/tree/master/reverse_words_in_a_string)
 #### [152. maximum product subarray](https://github.com/hitzzc/go-leetcode/tree/master/maximum_product_subarray)
+#### [153. find minimum in rotated sorted array](https://github.com/hitzzc/go-leetcode/tree/master/find_minimum_in_rotated_sorted_array)
 
 
 
diff --git a/find_minimum_in_rotated_sorted_array/find_minimum_in_rotated_sorted_array.go b/find_minimum_in_rotated_sorted_array/find_minimum_in_rotated_sorted_array.go
@@ -0,0 +1,22 @@
+package find_minimum_in_rotated_sorted_array
+
+func findMin(nums []int) int {
+	return helper(nums, 0, len(nums)-1)
+}
+
+func helper(nums []int, i, j int) int {
+	if i == j {
+		return nums[i]
+	}
+	if nums[i] < nums[j] {
+		return nums[i]
+	}
+	mid := i + (j-i)/2
+	if i == mid {
+		return helper(nums, i+1, j)
+	}
+	if nums[i] < nums[mid] {
+		return helper(nums, mid+1, j)
+	}
+	return helper(nums, i, mid)
+}
