Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 271
Good morning! Here's your coding interview problem for today.

This problem was asked by Netflix.

Given a sorted list of integers of length `N`, determine if an element `x` is in the list without performing any multiplication, division, or bit-shift operations.

Do this in **O(log N)** time.

Pull request description:
Day271
Resolves #553.

Patch:
diff --git a/README.md b/README.md
index 4dac06d..91ed69c 100644
--- a/README.md
+++ b/README.md
@@ -277,3 +277,4 @@ problems from
 * [Day 268](https://github.com/vaskoz/dailycodingproblem-go/issues/544)
 * [Day 269](https://github.com/vaskoz/dailycodingproblem-go/issues/547)
 * [Day 270](https://github.com/vaskoz/dailycodingproblem-go/issues/548)
+* [Day 271](https://github.com/vaskoz/dailycodingproblem-go/issues/553)
diff --git a/day271/problem.go b/day271/problem.go
new file mode 100644
index 0000000..73bcb69
--- /dev/null
+++ b/day271/problem.go
@@ -0,0 +1,29 @@
+package day271
+
+import "sort"
+
+// BinarySearch is a handwritten binary search.
+func BinarySearch(sorted []int, x int) int {
+	left, right := 0, len(sorted)-1
+	for left < right {
+		mid := (left + right) / 2
+		val := sorted[mid]
+		if x < val {
+			right = mid - 1
+		} else if x == val {
+			return mid
+		} else {
+			left = mid + 1
+		}
+	}
+	return -1
+}
+
+// BinarySearchSortPkg delegates to the sort package.
+func BinarySearchSortPkg(sorted []int, x int) int {
+	index := sort.SearchInts(sorted, x)
+	if sorted[index] == x {
+		return index
+	}
+	return -1
+}


Test patch:
diff --git a/day271/problem_test.go b/day271/problem_test.go
new file mode 100644
index 0000000..fddc4f1
--- /dev/null
+++ b/day271/problem_test.go
@@ -0,0 +1,47 @@
+package day271
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	sorted   []int
+	x        int
+	contains bool
+}{
+	{[]int{1, 10, 11, 12, 14, 15}, 11, true},
+	{[]int{1, 10, 11, 12, 14, 15}, 7, false},
+}
+
+func TestBinarySearch(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if index := BinarySearch(tc.sorted, tc.x); (index > 0) != tc.contains {
+			t.Errorf("TCID %d, expected %v, got %v", tcid, tc.contains, (index > 0))
+		}
+	}
+}
+
+func BenchmarkBinarySearch(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			BinarySearch(tc.sorted, tc.x)
+		}
+	}
+}
+
+func TestBinarySearchSortPkg(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if index := BinarySearchSortPkg(tc.sorted, tc.x); (index >= 0) != tc.contains {
+			t.Errorf("TCID %d, expected %v, got %v", tcid, tc.contains, (index > 0))
+		}
+	}
+}
+
+func BenchmarkBinarySearchSortPkg(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			BinarySearchSortPkg(tc.sorted, tc.x)
+		}
+	}
+}