添加二查查找的三种情况

byhieg · byhieg · commit b26e8b4d338b · 2017-03-29T23:15:10.000+08:00
diff --git a/src/main/java/cn/byhieg/algorithmtutorial/Find.java b/src/main/java/cn/byhieg/algorithmtutorial/Find.java
@@ -0,0 +1,83 @@
+package cn.byhieg.algorithmtutorial;
+
+/**
+ * Created by shiqifeng on 2017/3/29.
+ * Mail byhieg@gmail.com
+ */
+public class Find {
+
+
+    /**
+     * 二查查找算法，要求准确找到目标值，没有找到则是-1.
+     * 此方法保证在相同元素都满足条件时，取到的是最大的下标
+     * 时间复杂度 o(lgN)
+     * @param nums int型数组，要求有序
+     * @return 找到，返回下标，没找到，返回-1
+     */
+    public int binarySerachFind(int[] nums,int des) {
+        int length = nums.length;
+        int low = 0;
+        int high = length - 1;
+        while (low < high) {
+            int mid = low + (high - low) / 2;
+            if (nums[mid] == des) {
+                return mid;
+            } else if (nums[mid] < des) {
+                low = mid + 1;
+            } else{
+                high = mid - 1;
+            }
+        }
+        return -1;
+    }
+
+    /**
+     * 给定一个单调不降的数组，查找大于des条件的最小的数
+     * @param nums
+     * @param des
+     * @return
+     */
+    public int binarySearchMinFind(int[] nums, int des) {
+        int length = nums.length;
+        int low = 0;
+        int high = length - 1;
+        int mid ;
+        while (low < high) {
+            mid = (low + high) / 2;
+           if (nums[mid] <= des){
+               low = mid + 1;
+           }else{
+               high = mid;
+           }
+        }
+        if (nums[high] > des) return high;
+        return -1;
+    }
+
+    /**
+     * 给定一个单调不降的数组，查找小于des条件的最大的数
+     * @param nums
+     * @param des
+     * @return
+     */
+    public int binarySearchMaxFind(int[] nums, int des) {
+        int length = nums.length;
+        int low = 0;
+        int high = length - 1;
+        int mid;
+        int result = -1;
+        while (low < high) {
+            mid = low + (high - low + 1) / 2;
+            if (nums[mid] < des){
+                low = mid;
+            }else{
+                high = mid - 1;
+            }
+        }
+        if (nums[low] < des) return low;
+        return -1;
+    }
+
+
+
+}
diff --git a/src/main/java/cn/byhieg/collectiontutorial/maptutorial/HashMapExample.java b/src/main/java/cn/byhieg/collectiontutorial/maptutorial/HashMapExample.java
@@ -1,8 +1,6 @@
 package cn.byhieg.collectiontutorial.maptutorial;
 
-import java.util.HashMap;
-import java.util.Iterator;
-import java.util.Map;
+import java.util.*;
 
 /**
  * Created by shiqifeng on 2017/2/24.
diff --git a/src/test/java/cn/byhieg/algorithmtutorialtest/FindTest.java b/src/test/java/cn/byhieg/algorithmtutorialtest/FindTest.java
@@ -0,0 +1,34 @@
+package cn.byhieg.algorithmtutorialtest;
+
+import cn.byhieg.algorithmtutorial.Find;
+import junit.framework.TestCase;
+
+/**
+ * Created by shiqifeng on 2017/3/29.
+ * Mail byhieg@gmail.com
+ */
+public class FindTest extends TestCase {
+    int[] nums;
+    int result;
+    public void setUp() throws Exception {
+        super.setUp();
+        nums = new int[]{1};
+    }
+
+    public void tearDown() throws Exception {
+        System.out.println(result);
+    }
+
+//    public void testBinarySerachFind() throws Exception {
+//        result = new Find().binarySerachFind(nums,6);
+//    }
+////
+//    public void testBinarySearchMinFind() throws Exception {
+//        result = new Find().binarySearchMinFind(nums,1);
+//    }
+
+    public void testBinarySearchMaxFind() throws Exception {
+        result = new Find().binarySearchMaxFind(nums, 2);
+    }
+
+}
