Add search code

jbee37142 · jbee37142 · commit 58c25476ac36 · 2017-06-01T11:22:34.000+09:00
diff --git a/src/test/java/search/BinarySearchTest.java b/src/test/java/search/BinarySearchTest.java
@@ -1,7 +1,69 @@
 package search;
 
-/**
- * Created by Jbee on 2017. 6. 1..
- */
+import org.junit.Test;
+
+import static org.hamcrest.CoreMatchers.is;
+import static org.junit.Assert.assertThat;
+
 public class BinarySearchTest {
+
+    /*
+        TASK
+        binary search를 사용하여 O(log n)의 시간복잡도로 target을 찾는다.
+     */
+    @Test
+    public void test() {
+        int[] arr = new int[7];
+        arr[0] = 52;
+        arr[1] = 31;
+        arr[2] = 24;
+        arr[3] = 45;
+        arr[4] = 13;
+        arr[5] = 11;
+        arr[6] = 28;
+        assertThat(searchByRec(arr, 24), is(2));
+        assertThat(search(arr, 24), is(2));
+    }
+
+    // while version
+    private int search(int[] arr, int target) {
+        if (arr == null) return -1;
+        int left = 0;
+        int right = arr.length - 1;
+
+        while (left <= right) {
+            int mid = left + (right - left) / 2;
+            if (arr[mid] == target) {
+                return mid;
+            }
+
+            if (arr[mid] < target) {
+                left = mid;
+                right -= 1;
+            } else {
+                right = mid;
+                left += 1;
+            }
+        }
+        return -1;
+    }
+
+    //recursive version
+    private int searchByRec(int[] arr, int target) {
+        if (arr == null) return -1;
+        return searchRec(arr, 0, arr.length - 1, target);
+    }
+
+    private int searchRec(int[] arr, int left, int right, int target) {
+        if (left > right || left < 0 || right >= arr.length) return -1;
+        int mid = left + (right - left) / 2;
+
+        if (arr[mid] == target) {
+            return mid;
+        } else if (arr[mid] < target) {
+            return searchRec(arr, mid, right - 1, target);
+        } else {
+            return searchRec(arr, left + 1, mid, target);
+        }
+    }
 }
diff --git a/src/test/java/search/SearchIn2DTest.java b/src/test/java/search/SearchIn2DTest.java
@@ -0,0 +1,82 @@
+package search;
+
+import org.junit.Test;
+
+import static org.hamcrest.CoreMatchers.is;
+import static org.junit.Assert.assertThat;
+
+public class SearchIn2DTest {
+
+    /*
+        TASK
+        정렬된 2차원 배열에서 검색한다.
+        1. 각 row 별로 for-loop 돌면서 O(log n)의 sort을 한다.
+        2. O(n)
+     */
+
+    @Test
+    public void test() {
+        int[][] matrix = new int[5][5];
+        for (int i = 0; i < matrix[0].length; i++) {
+            for (int j = 0; j < matrix[0].length; j++) {
+                matrix[i][j] = i + j;
+            }
+        }
+        assertThat(getTargetPosition(matrix, 5), is(new Position(4,1)));
+    }
+
+    public Position getTargetPosition(int[][] matrix, int target) {
+        if (matrix == null) return null;
+
+        int row = matrix.length - 1;
+        int col = 0;
+
+        while (row >= 0 && col < matrix[0].length) {
+            if (matrix[row][col] == target) {
+                return new Position(row, col);
+            } else if (matrix[row][col] < target) {
+                col++;
+            } else {
+                row--;
+            }
+        }
+
+        return null;
+    }
+
+    public class Position {
+        int row;
+        int col;
+
+        public Position(int row, int col) {
+            this.row = row;
+            this.col = col;
+        }
+
+        @Override
+        public boolean equals(Object o) {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+
+            Position position = (Position) o;
+
+            if (row != position.row) return false;
+            return col == position.col;
+        }
+
+        @Override
+        public int hashCode() {
+            int result = row;
+            result = 31 * result + col;
+            return result;
+        }
+
+        @Override
+        public String toString() {
+            return "Position{" +
+                    "row=" + row +
+                    ", col=" + col +
+                    '}';
+        }
+    }
+}
