Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 58
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

An sorted array of integers was rotated an unknown number of times.

Given such an array, find the index of the element in the array in faster than linear time. If the element doesn't exist in the array, return null.

For example, given the array [13, 18, 25, 2, 8, 10] and the element 8, return 4 (the index of 8 in the array).

You can assume all the integers in the array are unique.

Pull request description:
Day58
Resolves #127 .

Patch:
diff --git a/README.md b/README.md
index 5787fc2..54fbb31 100644
--- a/README.md
+++ b/README.md
@@ -69,3 +69,4 @@ problems from
 * [Day 55](https://github.com/vaskoz/dailycodingproblem-go/issues/121)
 * [Day 56](https://github.com/vaskoz/dailycodingproblem-go/issues/123)
 * [Day 57](https://github.com/vaskoz/dailycodingproblem-go/issues/124)
+* [Day 58](https://github.com/vaskoz/dailycodingproblem-go/issues/127)
diff --git a/day58/problem.go b/day58/problem.go
new file mode 100644
index 0000000..a8ff039
--- /dev/null
+++ b/day58/problem.go
@@ -0,0 +1,31 @@
+package day58
+
+// IndexSortedRotated returns the index of a target in a sorted slice.
+// Runs in O(log N) time and O(1) space since the input slice is sorted.
+// Returns the index or -1 if it doesn't exist.
+func IndexSortedRotated(sorted []int, target int) int {
+	var low, mid, high int = 0, len(sorted) / 2, len(sorted)
+	for low < high {
+		if curr := sorted[mid]; curr == target {
+			return mid
+		} else if inRange(sorted[mid:high], target) {
+			low = mid
+			mid = (low + high) / 2
+		} else {
+			high = mid
+			mid = (low + high) / 2
+		}
+	}
+	return -1
+}
+
+func inRange(sorted []int, target int) bool {
+	if sorted[0] < sorted[len(sorted)-1] &&
+		target >= sorted[0] && target <= sorted[len(sorted)-1] {
+		return true
+	} else if sorted[0] > sorted[len(sorted)-1] &&
+		(target <= sorted[len(sorted)-1] || target >= sorted[0]) {
+		return true
+	}
+	return false
+}


Test patch:
diff --git a/day58/problem_test.go b/day58/problem_test.go
new file mode 100644
index 0000000..371bf5f
--- /dev/null
+++ b/day58/problem_test.go
@@ -0,0 +1,34 @@
+package day58
+
+import "testing"
+
+var testcases = []struct {
+	sorted   []int
+	target   int
+	expected int
+}{
+	{[]int{13, 18, 25, 2, 8, 10}, 8, 4},
+	{[]int{13, 18, 25, 27, 2, 8, 10}, 8, 5},
+	{[]int{13, 18, 25, 27, 2, 8, 10}, 18, 1},
+	{[]int{13, 18, 25, 27, 2, 8, 10}, 14, -1},
+	{[]int{13, 18, 25, 27, 30, 36, 54, 100, 2}, 2, 8},
+	{[]int{13, 18, 25, 27, 30, 36, 54, 100, 2}, 1, -1},
+	{[]int{13, 18, 25, 27, 30, 36, 54, 100, 2}, 13, 0},
+}
+
+func TestIndexSortedRotated(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if index := IndexSortedRotated(tc.sorted, tc.target); index != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, index)
+		}
+	}
+}
+
+func BenchmarkIndexSortedRotated(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			IndexSortedRotated(tc.sorted, tc.target)
+		}
+	}
+}