Binary search done.

I chose to use an iterative method, instead of recursion, to avoid
function stacks. Perhaps I should try recursive approach and compare the
results.

2 files changed, 108 insertions, 0 deletions

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/BinarySearch.java b/AlgoDesignAndTechniqueEdxJava/sources/BinarySearch.java
new file mode 100644
index 0000000..9eb5915
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/BinarySearch.java
@@ -0,0 +1,77 @@
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.util.StringTokenizer;
+
+public class BinarySearch {
+
+	public static void main(String[] args) {
+		FastScanner scanner = new FastScanner(System.in);
+		int n = scanner.nextInt();
+		int[] a = new int[n];
+		for (int i = 0; i < n; i++) {
+			a[i] = scanner.nextInt();
+		}
+		int m = scanner.nextInt();
+		int[] b = new int[m];
+		for (int i = 0; i < m; i++) {
+			b[i] = scanner.nextInt();
+		}
+		for (int i = 0; i < m; i++) {
+			// replace with the call to binarySearch when implemented
+			System.out.print(binarySearch(a, b[i]) + " ");
+		}
+
+	}
+
+	public static int binarySearch(int[] a, int key) {
+		int low = 0;
+		int high = a.length - 1;
+		int mid = 0;
+		boolean found = false;
+		while (low <= high) {
+			mid = (int) Math.floor(low + (high - low) / 2);
+			if (key == a[mid]) {
+				found = true;
+				return mid;
+			} else if (key < a[mid])
+				high = mid - 1;
+			else
+				low = mid + 1;
+		}
+		if (found)
+			return low - 1;
+		else
+			return -1;
+	}
+
+	static class FastScanner {
+		BufferedReader br;
+		StringTokenizer st;
+
+		FastScanner(InputStream stream) {
+			try {
+				br = new BufferedReader(new InputStreamReader(stream));
+			} catch (Exception e) {
+				e.printStackTrace();
+			}
+		}
+
+		String next() {
+			while (st == null || !st.hasMoreTokens()) {
+				try {
+					st = new StringTokenizer(br.readLine());
+				} catch (IOException e) {
+					e.printStackTrace();
+				}
+			}
+			return st.nextToken();
+		}
+
+		int nextInt() {
+			return Integer.parseInt(next());
+		}
+	}
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/BinarySearchTest.java b/AlgoDesignAndTechniqueEdxJava/tests/BinarySearchTest.java
new file mode 100644
index 0000000..59a1289
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/BinarySearchTest.java
@@ -0,0 +1,31 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class BinarySearchTest {
+
+	@Test
+	void test1() {
+		int[] a = {1, 5, 8, 12, 13};
+		assertEquals(2, BinarySearch.binarySearch(a, 8));
+	}
+
+	@Test
+	void test2() {
+		int[] a = {1, 5, 8, 12, 13};
+		assertEquals(0, BinarySearch.binarySearch(a, 1));
+	}
+
+	@Test
+	void test3() {
+		int[] a = {1, 5, 8, 12, 13};
+		assertEquals(-1, BinarySearch.binarySearch(a, 23));
+	}
+
+	@Test
+	void test4() {
+		int[] a = {1, 5, 8, 12, 13};
+		assertEquals(-1, BinarySearch.binarySearch(a, 11));
+	}
+
+}