Leetcode Lect3 二分法总结

二分法模板

非递归版本：

 1 public class Solution {
 2     /**
 3      * @param A an integer array sorted in ascending order
 4      * @param target an integer
 5      * @return an integer
 6      */
 7     public int findPosition(int[] nums, int target) {
 8         if (nums == null || nums.length == 0) {
 9             return -1;
10         }
11         
12         int start = 0, end = nums.length - 1;
13         // 要点1: start + 1 < end
14         while (start + 1 < end) {
15         // 要点2：start + (end - start) / 2
16             int mid = start + (end - start) / 2;
17             // 要点3：=, <, > 分开讨论，mid 不+1也不-1
18             if (nums[mid] == target) {
19                 return mid;
20             } else if (nums[mid] < target) {
21                 start = mid;
22             } else {
23                 end = mid;
24             }
25         }
26         
27         // 要点4: 循环结束后，单独处理start和end
28         if (nums[start] == target) {
29             return start;
30         }
31         if (nums[end] == target) {
32             return end;
33         }
34         return -1;
35     }
36 }

死循环的发生：when target is the last position of the range
nums = [1,1], target = 1
使用 start < end 无论如何都会出现死循环

递归版本：

 1 public class Solution{
 2     public int findPosition(int[] nums, int target){
 3         return binarySearch(nums, 0, nums.length-1, target);
 4     }
 5 
 6     public int binarySearch(int[] nums, int start, int end, int target){
 7         if(start>end)
 8             return(-1);
 9 
10         int mid=(start+end)/2;
11         if(nums[mid]==target)
12             return(mid);
13         if(nums[mid]<target)
14             return binarySearch(nums, mid+1, end, target);
15         else
16             return binarySearch(nums, start, mid-1, target);
17     }
18 }

常见问题

Q: 为什么要用 start + 1 < end？而不是 start < end 或者 start <= end？

A: 为了避免死循环。二分法的模板中，整个程序架构分为两个部分：

通过 while 循环，将区间范围从 n 缩小到 2 （只有 start 和 end 两个点）。
在 start 和 end 中判断是否有解。

start < end 或者 start <= end 在寻找目标最后一次出现的位置的时候，出现死循环。

Q: 为什么明明可以 start = mid + 1 偏偏要写成 start = mid?

A: 大部分时候，mid 是可以 +1 和 -1 的。在一些特殊情况下，比如寻找目标的最后一次出现的位置时，当 target 与 nums[mid] 相等的时候，是不能够使用 mid + 1 或者 mid - 1 的。因为会导致漏掉解。那么为了节省脑力，统一写成 start = mid / end = mid 并不会造成任何解的丢失，并且也不会损失效率——log(n) 和 log(n+1) 没有区别。

许多同学在写二分法的时候，都比较习惯性的写 while (start < end) 这样的循环条件。这样的写法及其容易出现死循环，导致 LintCode 上的测试“超时”（Time Limit Exceeded）。

什么情况下会出现死循环？

在做 last position of target 这种模型下的二分法时，使用 while (start < end) 就容易出现超时。

在线练习：http://www.lintcode.com/problem/last-position-of-target/

我们来看看会超时的代码：
Java版本：

int start = 0, end = nums.length - 1;
while (start < end) {
    int mid = start + (end - start) / 2;
    if (nums[mid] == target) {
        start = mid;
    } else if (nums[mid] < target) {
        start = mid + 1;
    } else {
        end = mid - 1;
    }
}

上面这份代码是大部分同学的实现方式。看上去似乎没有太大问题。我们来注意一下 `nums[mid] == target` 时候的处理。这个时候，因为 mid 这个位置上的数有可能是最后一个出现的target，所以不能写成 start = mid + 1（那样就跳过了正确解）。而如果是这样写的话，下面这组数据将出现超时(TLE)：

nums = [1,1], target = 1

将数据带入过一下代码：

start = 0, end = 1
while (0 < 1) {
     mid = 0 + (1 - 0) / 2 = 0
     if (nums[0] == 1) {
         start = 0;
     }
     ...
}

我们发现，start 将始终是 `0`。

出现这个问题的主要原因是，mid = start + (end - start) / 2 这种写法是偏向start的。也就是说 mid 是中间偏左的位置。这样导致如果 start 和 end 已经是相邻关系，会导致 start 有可能在一轮循环之后保持不变。

或许你会说，那么我改成 mid = (start + end + 1) / 2 是否能解决问题呢？没错，确实可以解决 last position of target 的问题，但是这样之后 first position of target 就超时了。我们比较希望能够有一个理想的模板，无论是 first position of target 还是 last position of target，代码的区别尽可能的小和容易记住。

类型1：裸题

704. Binary Search

 1 class Solution:
 2     def bd(self, nums, target, start, end):
 3         while(start+1<end):
 4             mid=(start+end)//2
 5             if(nums[mid]==target):
 6                 return mid
 7             if(nums[mid]>target):
 8                 end=mid
 9             if(nums[mid]<target):
10                 start=mid
11         if(nums[start]==target):
12             return start
13         if(nums[end]==target):
14             return end
15         return -1
16 
17     def search(self, nums, target):
18         """
19         :type nums: List[int]
20         :type target: int
21         :rtype: int
22         """
23         sl=len(nums)-1
24         if(sl==-1):
25             return -1
26         ans=self.bd(nums, target, 0, sl)
27         return ans

View Code

 1 class Solution {
 2     public int search(int[] nums, int target) {
 3         int start=0, end=nums.length-1;
 4         while(start+1<end){
 5             int mid=start+(end-start)/2;
 6             if(nums[mid]==target)
 7                 return mid;
 8             if(nums[mid]<target)
 9                 start=mid;
10             if(nums[mid]>target)
11                 end=mid;
12         }
13         if(nums[end]==target)
14             return(end);
15         if(nums[start]==target)
16             return(start);
17 
18         return(-1);
19     }
20 }

View Code

34. Find First and Last Position of Element in Sorted Array

其实稍微改改边界就行了，但是写起来坑很多....

 1 class Solution:
 2     def fbs(self, nums, target, start, end):
 3         tmp=999999
 4         while(start+1<end):
 5             mid=(start+end)//2
 6             if(nums[mid]==target):
 7                 tmp=mid
 8                 end=mid
 9             if(nums[mid]>target):
10                 end=mid
11             if(nums[mid]<target):
12                 start=mid
13         if(nums[start]==target):
14             tmp=min(tmp,start)
15         if(nums[end]==target):
16             tmp=min(tmp, end)
17         if(tmp==999999):
18             return -1
19         else:
20             return tmp
21 
22     def lbs(self, nums, target, start, end):
23         tmp=-1
24         while(start+1<end):
25             mid=(start+end)//2
26             if(nums[mid]==target):
27                 tmp=mid
28                 start=mid
29             if(nums[mid]>target):
30                 end=mid
31             if(nums[mid]<target):
32                 start=mid
33         if(nums[start]==target):
34             tmp=max(tmp,start)
35         if(nums[end]==target):
36             tmp=max(tmp, end)
37         return tmp
38 
39     def searchRange(self, nums, target):
40         """
41         :type nums: List[int]
42         :type target: int
43         :rtype: List[int]
44         """
45         if(len(nums)==0):
46             return([-1,-1])
47         fs=self.fbs(nums, target, 0, len(nums)-1)
48         ls=self.lbs(nums, target, 0, len(nums)-1)
49         return([fs, ls])

View Code

 1 class Solution {
 2     public int[] searchRange(int[] nums, int target) {
 3         int start, end, mid;
 4         int[] ans=new int[2];
 5         ans[0]=-1;  ans[1]=-1;
 6         if(nums.length==0)
 7             return(ans);
 8         
 9         start=0;  end=nums.length-1;
10         while(start+1<end){
11             mid=(start+end)/2;
12             if(nums[mid]==target)
13                 ans[0]=mid;
14             if(nums[mid]>=target)
15                 end=mid;
16             if(nums[mid]<target)
17                 start=mid;
18         }
19         if(nums[start]!=target && nums[end]!=target && ans[0]==-1)
20             return(ans);
21         if(nums[end]==target)
22             ans[0]=end;
23         if(nums[start]==target)
24             ans[0]=start;
25         
26         start=0;  end=nums.length-1;
27         while(start+1<end){
28             mid=(start+end)/2;
29             if(nums[mid]==target)
30                 ans[1]=mid;
31             if(nums[mid]>target)
32                 end=mid;
33             if(nums[mid]<=target)
34                 start=mid;
35         }
36         if(nums[start]==target)
37             ans[1]=Math.max(ans[1], start);
38         if(nums[end]==target)
39             ans[1]=Math.max(ans[1], end);
40         
41         return(ans);        
42     }
43 }
44 
45 
46 
47 注意几个极端数据：
48 [1,4] 4
49 [8] 8
50 [8,8] 8
51 [8,8,8] 8

View Code

类型2：OOXX
给定一个数组（数据类似OOOOOOXXXXXXXXX），求数组中第一个/最后一个满足某个条件（X）的位置

278. First Bad Version

还是用二分法，把条件魔改一下就行了

改成while(start<end)是为了不漏掉剩余区间长度为2的情况。同时为了防止死循环，start也得改成mid+1

 1 # The isBadVersion API is already defined for you.
 2 # @param version, an integer
 3 # @return a bool
 4 # def isBadVersion(version):
 5 
 6 class Solution:
 7     def bs(self, start, end):
 8         cnt=0
 9         while(start<end):
10             mid=(start+end)//2
11             cnt+=1
12             print(start,end,mid,cnt)
13             if(isBadVersion(mid)):
14                 end=mid
15             else:
16                 start=mid+1
17         return start
18 
19     def firstBadVersion(self, n):
20         """
21         :type n: int
22         :rtype: int
23         """
24         if(n<=1):
25             return n
26         return self.bs(1,n)

View Code

还用原来的二分模板也可以....但要注意mid=start+(end-start)/2，防止溢出

 1 /* The isBadVersion API is defined in the parent class VersionControl.
 2       boolean isBadVersion(int version); */
 3 
 4 public class Solution extends VersionControl {
 5     public int firstBadVersion(int n) {
 6         int start=1,end=n,mid=-1;
 7         
 8         while(start+1<end){
 9             mid=start+(end-start)/2;
10             if(isBadVersion(mid))
11                 end=mid;
12             else
13                 start=mid;
14         }
15         if(isBadVersion(start))
16             return(start);
17         if(isBadVersion(end))
18             return(end);
19         return(mid);
20     }
21 }

View Code

658. Find K Closest Elements

先用二分找到数组内离target最近的元素下标，然后用O(k)的时间，用两个指针从中间向外扩展再找离得最近的k-1个元素即可。最后排个序输出

 1 class Solution:
 2     def bs(self, x, arr, start, end):
 3         while (start+1<end):
 4             mid=(start+end)//2
 5             if(arr[mid]==x):
 6                 return mid
 7             if(arr[mid]<x):
 8                 start=mid
 9             if(arr[mid]>x):
10                 end=mid
11         ansx=abs(arr[start]-x)
12         ans=start
13         while (ans<end and abs(arr[ans+1]-x)<ansx):
14             ans+=1
15             ansx=abs(arr[ans]-x)
16         return ans
17 
18 
19     def findClosestElements(self, arr, k, x):
20         """
21         :type arr: List[int]
22         :type k: int
23         :type x: int
24         :rtype: List[int]
25         """
26         pos=self.bs(x, arr, 0, len(arr)-1)
27         print(pos)
28         pl=pos-1
29         pr=pos+1
30         tk=k-1
31         ans=[arr[pos]]
32         while(tk):
33             if(pl<0 and pr<=len(arr)-1):
34                 ans.append(arr[pr])
35                 pr+=1
36             if(pl>=0 and pr>len(arr)-1):
37                 ans.append(arr[pl])
38                 pl-=1
39             if(pl>=0 and pr<=len(arr)-1):
40                 if(abs(arr[pr]-x)<abs(arr[pl]-x)):
41                     ans.append(arr[pr])
42                     pr+=1
43                 else:
44                     ans.append(arr[pl])
45                     pl-=1
46             tk-=1
47         ans.sort()
48         return ans
49 
50 sl=Solution()
51 aa=[0,0,0,1,3,5,6,7,8,8]
52 print(sl.findClosestElements(aa,2,2))

View Code

 1 class Solution {
 2     public List<Integer> findClosestElements(int[] arr, int k, int x) {
 3         List<Integer> ans=new ArrayList<>();
 4         int start=0,end=arr.length-1,mid=-1;
 5         boolean found=false;
 6         while(start+1<end){
 7             mid=start+(end-start)/2;
 8             if(arr[mid]==x){
 9                 found=true;
10                 break;
11             }
12             if(arr[mid]<x)
13                 start=mid;
14             if(arr[mid]>x)
15                 end=mid;
16         }
17         if(arr[start]==x){
18             found=true;
19             mid=start;
20         }
21         if(arr[end]==x){
22             found=true;
23             mid=end;
24         }
25         if(!found){
26             if(x>arr[arr.length-1])
27                 mid=end;
28             else if(x<arr[0])
29                 mid=start;
30             else{
31                 if(x-arr[start]<=arr[end]-x)
32                     mid=start;
33                 else
34                     mid=end;
35             }
36         }
37         System.out.println(mid);
38         
39         ans.add(arr[mid]);
40         int pl=mid-1,pr=mid+1,cnt=0;
41         while(cnt<k-1){
42             if(pl<0){
43                 ans.add(arr[pr]);
44                 pr++;
45             }
46             else if(pr>=arr.length){
47                 ans.add(arr[pl]);
48                 pl--;
49             }
50             else if(x-arr[pl]<=arr[pr]-x){
51                 ans.add(arr[pl]);
52                 pl--;
53             }
54             else{
55                 ans.add(arr[pr]);
56                 pr++;
57             }
58             cnt++;
59         }
60         Collections.sort(ans);
61         return(ans);
62     }
63 }

View Code

852. Peak Index in a Mountain Array

ooooPxxxxx题，一样的套路

o: 单调递增 x: 单调递减

注意处理mid正好是peak的情况

 1 class Solution:
 2     def peakIndexInMountainArray(self, A):
 3         """
 4         :type A: List[int]
 5         :rtype: int
 6         """
 7         la=len(A)
 8         start=0
 9         end=la-1
10         while(start+1<end):
11             mid=(start+end)//2
12             if(A[mid-1]<A[mid] and A[mid]>A[mid+1]):
13                 return mid
14             if(A[mid-1]<A[mid] and A[mid]<A[mid+1]):
15                 start=mid
16             if(A[mid-1]>A[mid] and A[mid]>A[mid+1]):
17                 end=mid
18         return (start if A[start]>A[end] else end)

View Code

 1 class Solution {
 2     public int peakIndexInMountainArray(int[] A) {
 3         int start=0,end=A.length,mid;
 4         while(start+1<end){
 5             mid=start+(end-start)/2;
 6             if(A[mid-1]<A[mid] && A[mid]>A[mid+1])
 7                 return(mid);
 8             if(A[mid-1]<A[mid] && A[mid]<A[mid+1])
 9                 start=mid;
10             if(A[mid-1]>A[mid] && A[mid]>A[mid+1])
11                 end=mid;
12         }
13         if(start>0 && (A[start-1]<A[start] && A[start]>A[start+1]))
14             return(start);
15         if(end<A.length-1 && (A[end-1]<A[end] && A[end]>A[end+1]))
16             return(end);
17         return(-1);
18     }
19 }

View Code

74. Search a 2D Matrix

二分两遍。第一遍找在哪一行，第二遍找具体的value

第一遍找哪一行的时候，注意对最后剩下的start和end的判断。我的理解是二分查找的while搜完之后start和end会正好卡在距离target最近的值左右。（要么是A[start]<=target && A[end]>=target，要么是A[start]>=target，要么是A[end]<=target，分别想一下即可）

 1 class Solution:
 2     def bs(self, nums, _start, _end, target, R):
 3         start=_start
 4         end=_end
 5         while(start+1<end):
 6             mid=(start+end)//2
 7             if(nums[mid]>target):
 8                 end=mid
 9             if(nums[mid]<target):
10                 start=mid
11             if(nums[mid]==target):
12                 return mid
13         if(R==1):        #search for value
14             if(nums[start]==target):
15                 return start
16             if(nums[end]==target):
17                 return end
18             return -1
19         if(R==0):        #search for range
20             if(nums[start]<=target and nums[end]>target):
21                 return start
22             if(nums[end]<=target):
23                 return end
24             else:
25                 return -1
26 
27     def searchMatrix(self, mm, target):
28         """
29         :type mm: List[List[int]]
30         :type target: int
31         :rtype: bool
32         """
33         if(len(mm)==0):
34             return False
35         ml=len(mm[0])
36         if(ml==0):
37             return False
38         fst=[xx[0] for xx in mm]
39         rg=self.bs(fst,0,len(fst)-1,target,0)
40         print(rg)
41         ans=self.bs(mm[rg],0,ml-1,target,1)
42         if(ans==-1):
43             return False
44         else:
45             return True
46 
47 sl=Solution()
48 mm=[[5,6,7,8]]
49 print(sl.searchMatrix(mm,8))

View Code

 1 class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         int start,end,mid,idx;
 4         int lx=matrix.length;
 5         if(lx==0) return(false);
 6         int ly=matrix[0].length;
 7         if(ly==0) return(false);
 8         
 9         start=0;  end=lx-1;
10         while(start+1<end){
11             mid=(start+end)/2;
12             if(matrix[mid][0]==target)
13                 return(true);
14             if(matrix[mid][0]<target)
15                 start=mid;
16             if(matrix[mid][0]>target)
17                 end=mid;
18         }
19         if(matrix[start][0]>target)
20             return(false);
21         if(matrix[end][0]<=target)
22             idx=end;
23         else
24             idx=start;
25         
26         start=0;  end=ly-1;
27         while(start+1<end){
28             mid=(start+end)/2;
29             if(matrix[idx][mid]==target)
30                 return(true);
31             if(matrix[idx][mid]<target)
32                 start=mid;
33             if(matrix[idx][mid]>target)
34                 end=mid;
35         }
36         if(matrix[idx][start]==target || matrix[idx][end]==target)
37             return(true);
38         else
39             return(false);
40     }
41 }

View Code

240. Search a 2D Matrix II

这题其实不是二分....

O(M+N)的方法：类似dp一样转移当前位置

[i][j] -> [i][j+1] , if A[i][j]<target
          [i-1][j] , if A[i][j]>target

初始放在最左下角，即[len(A)-1][0]处

 1 class Solution:
 2     def searchMatrix(self, matrix, target):
 3         """
 4         :type matrix: List[List[int]]
 5         :type target: int
 6         :rtype: bool
 7         """
 8         lm=len(matrix)
 9         if(lm==0):
10             return False
11         ln=len(matrix[0])
12         if(ln==0):
13             return False
14 
15         tx=lm-1
16         ty=0
17         for i in range(0,lm+ln):
18             if(tx<0 or ty>=ln):
19                 return False
20             tmp=matrix[tx][ty]
21             #print(tx,ty,tmp)
22             if(tmp==target):
23                 return True
24             if(tmp>target):
25                 tx-=1
26             if(tmp<target):
27                 ty+=1
28 
29 sl=Solution()
30 sl.searchMatrix([[1]],1)

View Code

 1 class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         int lx=matrix.length-1;
 4         if(lx<0) return(false);
 5         int ly=matrix[0].length-1;
 6         if(ly<0) return(false);
 7         
 8         int px=lx,py=0;
 9         while(px>=0 && py<=ly){
10             if(px>0 && matrix[px][py]>target)
11                 px-=1;
12             else if(matrix[px][py]==target)
13                 return(true);
14             else if(py<ly && matrix[px][py]<target)
15                 py+=1;
16             else
17                 return(false);
18         } 
19         return(false);
20     }
21 }

View Code

https://www.lintcode.com/problem/search-for-a-range/description

同LeetCode 34. Find First and Last Position of Element in Sorted Array , 往上滑滚动条就有......

https://www.lintcode.com/problem/total-occurrence-of-target/

没权限呜呜呜...

302 Smallest Rectangle Enclosing Black Pixels

传送门：https://www.lintcode.com/problem/smallest-rectangle-enclosing-black-pixels/description

类型3：

162. Find Peak Element

看似一头雾水，其实yy一下就行了...

因为左端和右端都是负无穷，所以peak肯定是存在的。然后在二分法中，因为mid肯定是夹在start和end中间的，所以直接讨论4种情况：

nums[mid-1]<nums[mid]>nums[mid+1]　　直接输出完事了
nums[mid-1]<nums[mid]<nums[mid+1]　　start:=mid，去找右边那个peak
nums[mid-1]>nums[mid]>nums[mid+1]　　end:=mid，去找左边那个peak
nums[mid-1]>nums[mid]<nums[mid+1]　　两边都有peak，随便start:=mid或者end:=mid都可以

 1 class Solution {
 2     public int findPeakElement(int[] nums) {
 3         if(nums.length==1)
 4             return(0);
 5         
 6         int l=0,r=nums.length-1,mid=-1;
 7         while(l+1<r){
 8             mid=l+(r-l)/2;
 9             if(nums[mid-1]<nums[mid] && nums[mid]<nums[mid+1])
10                 l=mid;
11             else if(nums[mid-1]<nums[mid] && nums[mid]>nums[mid+1])
12                 return(mid);
13             else
14                 r=mid;
15         }
16         
17         if(nums[l]>nums[r])
18             return(l);
19         else
20             return(r);
21     }
22 }

View Code

33. Search in Rotated Sorted Array

三次二分...但加起来还是算logN嘛【摊手

第一次：找数组中的最小值，记最小值的下标为idx

 1 将rotated array的数据值按xy坐标系画出来看一哈，大概是这样的：
 2 
 3                  '   |
 4               '      |
 5            '         |
 6   '[fst]            |
 7 ---------------------------------------------------------------
 8                      |                       '[lst]
 9                      |                    '
10                      |                 '
11                      |             '
12                      |  '[最小]
13 
14 可以发现，最小值左半边的数都是>=first的，最小值及其右半边的数都是<=lst的
15 按照OOOOXXXX的思路，通过二分缩小start~end的范围。注意循环里不需要判断mid是不是最小值点了（因为不好判断）
16 最后退出循环时，start~end的区间范围最多是2，且其中肯定包含最小值。手动min判断一下即可
17 
18 
19     def findmin(self, nums):    #return index of min value
20         nl=len(nums)
21         fst=nums[0]
22         lst=nums[nl-1]
23         start=0
24         end=nl-1
25         while(start+1<end):
26             mid=(start+end)//2
27             if(nums[mid]>=fst):
28                 start=mid
29             if(nums[mid]<=lst):
30                 end=mid
31         return(start if nums[start]<nums[end] else end)

第二次：在有序数组nums[0..idx-1]中找target

第三次：在有序数组nums[idx..len-1]中找target

 1 class Solution:
 2 
 3     def findmin(self, nums):    #return index of min value
 4         nl=len(nums)
 5         fst=nums[0]
 6         lst=nums[nl-1]
 7         start=0
 8         end=nl-1
 9         while(start+1<end):
10             mid=(start+end)//2
11             if(nums[mid]>=fst):
12                 start=mid
13             if(nums[mid]<=lst):
14                 end=mid
15         return(start if nums[start]<nums[end] else end)
16 
17     def bs(self, nums, _start, _end, target):
18         start=_start
19         end=_end
20         while(start+1<end):
21             mid=(start+end)//2
22             if(nums[mid]==target):
23                 return mid
24             if(nums[mid]<target):
25                 start=mid
26             if(nums[mid]>target):
27                 end=mid
28         if(nums[start]==target):
29             return start
30         if(nums[end]==target):
31             return end
32         return -1
33 
34     def search(self, nums, target):
35         """
36         :type nums: List[int]
37         :type target: int
38         :rtype: int
39         """
40         if(len(nums)==0):
41             return -1
42         if(len(nums)==1):
43             return(0 if nums[0]==target else -1)
44         idx=self.findmin(nums)
45         #print(idx)
46         ans1=self.bs(nums,0,idx-1,target) if idx>0 else -1
47         #print(0,idx-1,ans1,nums)
48         ans2=self.bs(nums,idx,len(nums)-1,target) if idx<=len(nums)-1 else -1
49         #print(idx,len(nums)-1,ans2,nums)
50         return (ans1 if ans1!=-1 else ans2)
51 
52 sl=Solution()
53 print(sl.search([3,1], 1))

View Code

 1 class Solution {
 2     public int binsearch(int x, int y, int[] nums, int target){
 3         int start=x, end=y, mid=-1;
 4         while(start+1<end){
 5             mid=start+(end-start)/2;
 6             if(nums[mid]==target)
 7                 return(mid);
 8             if(nums[mid]<target)
 9                 start=mid;
10             if(nums[mid]>target)
11                 end=mid;
12         }
13         if(nums[start]==target)
14             return(start);
15         else if(nums[end]==target)
16             return(end);
17         else
18             return(-1);        
19     }
20     
21     public int search(int[] nums, int target) {
22         if(nums.length==0)
23             return(-1);
24         int start=0,end=nums.length-1,mid=-1;
25         int fst=nums[0], lst=nums[end];
26         while(start+1<end){
27             mid=start+(end-start)/2;
28             if(nums[mid]>fst)
29                 start=mid;
30             if(nums[mid]<lst)
31                 end=mid;
32         }
33         fst=start;    lst=end;
34         //[0..fst] / [lst..length-1]
35         
36         int ans=binsearch(0, fst, nums, target);
37         if(ans!=-1)
38             return(ans);
39         return(binsearch(lst, nums.length-1, nums, target));
40     }
41 }

View Code

补充：快速幂

https://leetcode.com/problems/powx-n/

 1 class Solution:
 2     def myPow(self, x, n):
 3         """
 4         :type x: float
 5         :type n: int
 6         :rtype: float
 7         """
 8         inc=x
 9         ans=1
10         N=int(n)
11         flag=False
12         if(N==0):
13             return 1
14         if(N<0):
15             N=-N
16             flag=True
17         while(N>1):
18             if(N%2!=0):
19                 ans=ans*inc
20             inc=inc*inc
21             N=N//2
22             #print(inc,ans,N)
23         ans=inc*ans
24         if(flag):
25             ans=1/ans
26         return ans
27 
28 sl=Solution()
29 xx=sl.myPow(2,-2)
30 print(xx)

View Code

类型4：二分答案

Copy Books

https://www.lintcode.com/problem/copy-books/description

三步翻转法

http://www.lintcode.com/problem/recover-rotated-sorted-array/

题意：对于类似4,5,1,2,3的数组，in place还原成1,2,3,4,5

sol：先找到5和1之间的这个位置（可以用二分法），然后按以下策略翻转数组：

1. 分别翻转两部分

45123

54321

2. 翻转整个数组

54321

12345

http://www.lintcode.com/problem/rotate-string/

abcde fg -> edcba gf

edcbagf -> fgabcde

二维矩阵找数问题

240. Search a 2D Matrix II

前面做过啦往上翻！ (‾◡◝)

辗转相除法

辗转相除法，又名欧几里德算法，是求最大公约数的一种方法。它的具体做法是：用较大的数除以较小的数，再用除数除以出现的余数（第一余数），再用第一余数除以出现的余数（第二余数），如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

1 public int gcd(int big, int small) {
2     if (small != 0) {
3         return gcd(small, big % small);
4     } else {
5         return big;
6     }
7 }

http://www.lintcode.com/problem/greatest-common-divisor/

快速幂算法

递归版本：

 1 int power(int x, int n) {
 2     if (n == 0) return 1;
 3     if (n % 2 == 0) {
 4         int tmp = power(x, n / 2);
 5         return tmp * tmp;
 6     } else {
 7         int tmp = power(x, n / 2);
 8         return tmp * tmp * x;
 9     }
10 }

非递归版本：

 1 int power(int x, int n) {
 2     int ans = 1, base = x;
 3     while (n != 0) {
 4         if (n % 2 == 1) {
 5             ans *= base;
 6         }
 7         base *= base;
 8         n = n / 2;
 9     }
10     return ans;
11 }

非递归版本与递归版本原理相同，计算顺序略有不同。

因为递归是从大问题进入，划分子问题然后层层返回再求解大问题。这里要从小问题开始，直接求解大问题。
你可以打印出每次循环中

递归版本和非递归版本都应该熟练掌握，虽然递归版本更容易掌握和理解，且logN的计算深度也不会导致 Stack Overflow。但是面试官是很有可能为了加大难度让你在用非递归的版本写一遍的。

http://www.lintcode.com/problem/fast-power/
http://www.lintcode.com/problem/powx-n/

两个排序数组的中位数

在两个排序数组中，求他们合并到一起之后的中位数

时间复杂度要求：O(log(n+m))，其中 n, m 分别为两个数组的长度

http://www.lintcode.com/problem/median-of-two-sorted-arrays/

这个题有三种做法：

基于 FindKth 的算法。整体思想类似于 median of unsorted array 可以用 find kth from unsorted array 的解题思路。
基于中点比较的算法。一头一尾各自丢掉一些，去掉一半的时候，整个问题的形式不变。可以推广到 median of k sorted arrays.
基于二分的方法。二分 median 的值，然后再用二分法看一下两个数组里有多少个数小于这个二分出来的值