summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-10-05 21:57:16 -0500
committerHaidong Ji2018-10-05 21:57:16 -0500
commit948cfbc5364931ec98112d89690472a6d457fcdb (patch)
tree1ad447366eedc1cbf48ff1549a2e611376ed8e96
parent109ade52e695184b54c68ff5426a8672d7443047 (diff)
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.
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/BinarySearch.java77
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/BinarySearchTest.java31
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));
+ }
+
+}