Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 203
Good morning! Here's your coding interview problem for today.

This problem was asked by Uber.

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element in O(log N) time. You may assume the array does not contain duplicates.

For example, given `[5, 7, 10, 3, 4]`, return `3`.

Pull request description:
Day203
Resolves #419.

Patch:
diff --git a/README.md b/README.md
index 15ae13e..503807c 100644
--- a/README.md
+++ b/README.md
@@ -213,3 +213,4 @@ problems from
 * [Day 200](https://github.com/vaskoz/dailycodingproblem-go/issues/411)
 * [Day 201](https://github.com/vaskoz/dailycodingproblem-go/issues/415)
 * [Day 202](https://github.com/vaskoz/dailycodingproblem-go/issues/417)
+* [Day 203](https://github.com/vaskoz/dailycodingproblem-go/issues/419)
diff --git a/day203/problem.go b/day203/problem.go
new file mode 100644
index 0000000..7c8c485
--- /dev/null
+++ b/day203/problem.go
@@ -0,0 +1,17 @@
+package day203
+
+// FindSmallestOnRotated is binary search for the smallest value
+// on a sorted but rotated slice.
+// Runs in O(log N) time and O(1) space.
+func FindSmallestOnRotated(nums []int) int {
+	left, right := 0, len(nums)-1
+	for left < right {
+		mid := (left + right) / 2
+		if nums[mid] < nums[right] {
+			right = mid
+		} else {
+			left = mid + 1
+		}
+	}
+	return nums[left]
+}


Test patch:
diff --git a/day203/problem_test.go b/day203/problem_test.go
new file mode 100644
index 0000000..7b22cba
--- /dev/null
+++ b/day203/problem_test.go
@@ -0,0 +1,32 @@
+package day203
+
+import "testing"
+
+var testcases = []struct {
+	nums     []int
+	smallest int
+}{
+	{[]int{5, 7, 10, 3, 4}, 3},
+	{[]int{3, 4, 5, 7, 10}, 3},
+	{[]int{10, 3, 4, 5, 7}, 3},
+	{[]int{7, 10, 3, 4, 5}, 3},
+	{[]int{4, 5, 7, 10, 3}, 3},
+	{[]int{4, 4, 4, 4, 3}, 3},
+}
+
+func TestFindSmallestOnRotated(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if smallest := FindSmallestOnRotated(tc.nums); smallest != tc.smallest {
+			t.Errorf("Expected %v, got %v", tc.smallest, smallest)
+		}
+	}
+}
+
+func BenchmarkFindSmallestOnRotated(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			FindSmallestOnRotated(tc.nums)
+		}
+	}
+}