Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 273
Good morning! Here's your coding interview problem for today.

This problem was asked by Apple.

A fixed point in an array is an element whose value is equal to its index. Given a sorted array of distinct elements, return a fixed point, if one exists. Otherwise, return False.

For example, given `[-6, 0, 2, 40]`, you should return `2`. Given `[1, 5, 7, 8]`, you should return `False`.

Pull request description:
Day273
Resolves #556.

Patch:
diff --git a/README.md b/README.md
index 6e819b2..2b80f07 100644
--- a/README.md
+++ b/README.md
@@ -279,3 +279,4 @@ problems from
 * [Day 270](https://github.com/vaskoz/dailycodingproblem-go/issues/548)
 * [Day 271](https://github.com/vaskoz/dailycodingproblem-go/issues/553)
 * [Day 272](https://github.com/vaskoz/dailycodingproblem-go/issues/555)
+* [Day 273](https://github.com/vaskoz/dailycodingproblem-go/issues/556)
diff --git a/day273/problem.go b/day273/problem.go
new file mode 100644
index 0000000..777c553
--- /dev/null
+++ b/day273/problem.go
@@ -0,0 +1,28 @@
+package day273
+
+import "errors"
+
+var errNoFixedPoint = errors.New("no fixed point found")
+
+// ErrNoFixedPoint returns the error associated with no fixed point in the input.
+func ErrNoFixedPoint() error {
+	return errNoFixedPoint
+}
+
+// FindFixedPoint returns the fixed point number/index if it exists.
+// Otherwise, it returns an error if it doesn't exist.
+// Runs in O(log N) time and O(1) space.
+func FindFixedPoint(sorted []int) (int, error) {
+	left, right := 0, len(sorted)
+	for left < right {
+		switch mid := (left + right) / 2; {
+		case mid == sorted[mid]:
+			return mid, nil
+		case mid < sorted[mid]:
+			right = mid
+		default:
+			left = mid
+		}
+	}
+	return 0, errNoFixedPoint
+}


Test patch:
diff --git a/day273/problem_test.go b/day273/problem_test.go
new file mode 100644
index 0000000..a9413b4
--- /dev/null
+++ b/day273/problem_test.go
@@ -0,0 +1,31 @@
+package day273
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	sorted      []int
+	expected    int
+	expectedErr error
+}{
+	{[]int{-6, 0, 2, 40}, 2, nil},
+	{[]int{1, 5, 7, 8}, 0, ErrNoFixedPoint()},
+	{[]int{-10, -1, 0, 3, 10, 11, 30, 50, 100}, 3, nil},
+}
+
+func TestFindFixedPoint(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, err := FindFixedPoint(tc.sorted); result != tc.expected || err != tc.expectedErr {
+			t.Errorf("Expected (%v,%v), got (%v,%v)", tc.expected, tc.expectedErr, result, err)
+		}
+	}
+}
+
+func BenchmarkFindFixedPoint(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			FindFixedPoint(tc.sorted)
+		}
+	}
+}