二分查找变异写法

randian666 · randian666 · commit 5c6bbcb51492 · 2019-01-28T00:09:10.000+08:00
diff --git a/README.md b/README.md
@@ -167,7 +167,7 @@
  - 一个在线文档系统，文档可以被编辑，如何防止多人同时对同
  - 一份文档进行编辑更新。
  - 线上系统突然变得异常缓慢，你如何查找问题。
- - [说说你平时用到的设计模式](http://tech.hunts.work/2015/09/01/%E7%B3%BB%E7%BB%9F%E6%9E%B6%E6%9E%84/%E7%B3%BB%E7%BB%9F%E6%9E%B6%E6%9E%84-%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/#2-%E7%AE%80%E5%8D%95%E5%B7%A5%E5%8E%82simple-factory)。
+ - [说说你平时用到的设计模式](https://github.com/Snailclimb/JavaGuide/blob/master/Java%E7%9B%B8%E5%85%B3/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F.md)。
  - [Dubbo的原理，有看过源码么，数据怎么流转的，怎么实现集群，负载均衡，服务注册和发现，重试转发，快速失败的策略是怎样的 。](https://blog.csdn.net/he90227/article/details/70157046/)
  - 一次RPC请求的流程是什么。
  - [自己实现过rpc么，原理可以简单讲讲。Rpc要解决什么问题。](https://mp.weixin.qq.com/s/kHcbIgMFNB0np6olcPch4w)
diff --git a/src/main/java/com/algorithm/study/demo/algorithm/FindProject.java b/src/main/java/com/algorithm/study/demo/algorithm/FindProject.java
@@ -14,8 +14,8 @@
 public class FindProject {
     public static void main(String[] args) {
 
-        int[] is=new int[]{3,5,6,7,10};
-        System.out.println(binary_search_xiaoyu(is,10));
+        int[] is=new int[]{4,5,6,7,0,1,2};
+        System.out.println(binary_search_33(is,4));
 //        System.out.println(binarySearch(is,2));
 //        Shape redRectangle = new RedShapeDecorator(new Rectangle());
 //        redRectangle.doShaper();
@@ -213,4 +213,42 @@ public static int binary_search_xiaoyu(int[] srcArray,int des){
         }
         return -1;
     }
+
+    /**
+     * 假设按照升序排序的数组在预先未知的某个点上进行了旋转
+     * ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
+     * 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
+     * @return
+     */
+    public static int binary_search_33(int[] nums,int target){
+        if (nums.length==0) return -1;
+        if (nums.length==1){
+            if (nums[0]==target){
+                return 0;
+            }else{
+                return -1;
+            }
+        }
+        int left=0;
+        int right=nums.length-1;
+        int middle=0;
+        while (left<=right){
+            middle=(left+right)>>1;
+            if (nums[middle]==target) return middle;
+            if (nums[middle]>=nums[right]){
+                if(nums[left]<=target&&target<nums[middle]){
+                    right = middle-1;
+                }else{
+                    left = middle+1;
+                }
+            }else{
+                if(nums[middle]<target&&target<=nums[right]){
+                    left = middle+1;
+                }else{
+                    right = middle==0?middle:middle-1;
+                }
+            }
+        }
+        return -1;
+    }
 }
