fixed pezy#11

pezy · pezy · commit 19a68568114b · 2015-04-13T11:03:44.000+08:00
diff --git a/067. Search for a Range/README.md b/067. Search for a Range/README.md
@@ -22,3 +22,21 @@ if (A[0] == A[n-1] && A[0] == target) return vector<int>{0, n-1};
 ```
 
 方法不惊艳，希望有更好解法的能告诉我。
+
+-----
+
+在 [issue #11](https://github.com/pezy/LeetCode/issues/11) 中，@ender233 告诉了我一个更好的思路。
+
+他的本质思想，是用三次**二分查找**来避免最坏情况。但后两次，皆为二分查找的变种，即查找的不是目标，而是目标应该插入的位置。
+
+这个"变种"的二分查找我尝试写了一下，判断要多得多，而且写的很丑。智商捉急且懒散成性的情况下，我略改了一下思路：
+
+既然二分法可以从根本上将 O(n) 的情况减少到 O(logn) 的层次，那么三次二分与多次二分，差别其实并不大。(仍处于 O(logn) 的级别)
+
+那么：
+
+- 第一次二分，找到 target, 以及 `iPos`。
+- 接着二分左边 [0, iPos-1], 以及右边 [iPos+1, n-1]。依然找 target, 左边位置设为 `lo`(low), 右边位置设为 `hi`(high).
+- 不断循环往左、右二分查找 target，直到找不到为止。那么此刻范围也就确定好了。
+
+代码已更新。这样效率的确高，我去 LeetCode 试了一下，15ms, 属于 C++ 目前最高效率。
diff --git a/067. Search for a Range/solution.h b/067. Search for a Range/solution.h
@@ -3,20 +3,23 @@
 using std::vector;
 
 class Solution {
+    int binarySearch(int A[], int l, int r, int target) {
+        for (int mid; l <= r; ) {
+            mid = ( l + r ) >> 1;
+            if      ( A[mid] < target ) l = mid + 1;
+            else if ( A[mid] > target ) r = mid - 1;
+            else return mid;
+        }
+        return -1;
+    }
 public:
     vector<int> searchRange(int A[], int n, int target) {
-        if (A[0] == A[n-1] && A[0] == target) return vector<int>{0, n-1};
-        vector<int> retv{-1, -1};
-        for (int i=0, j=n-1; i<=j; ) {
-            int mid = (i + j) >> 1;
-            if (target == A[mid]) {retv[0] = retv[1] = mid; break;}
-            else if (target < A[mid]) j = mid-1;
-            else i = mid + 1;
+        int iPos = binarySearch( A, 0, n-1, target ), l = -1, r = -1;
+        if ( iPos != -1 ) {
+            l = r = iPos;
+            for (int lo = l; (lo = binarySearch(A, 0,   lo-1, target)) != -1; l = lo ) ;
+            for (int hi = r; (hi = binarySearch(A, hi+1, n-1, target)) != -1; r = hi ) ;
         }
-        while (retv[0]>0 && A[retv[0]-1] == target)
-            --retv[0];
-        while (retv[1]<n-1 && A[retv[1]+1] == target)
-            ++retv[1];
-        return retv;
+        return {l ,r};
     }
 };
