binary search完整笔记

1 Search in Rotated Sorted Array

二分搜索，注意分清各种情况

 1 public class Solution {
 2     public int search(int[] nums, int target) {
 3         int i = 0, j = nums.length - 1;
 4         while (i + 1 < j) {
 5             int mid = i + (j - i) / 2;
 6             if (nums[mid] == target) {
 7                 return mid;
 8             }
 9             
10             if (nums[mid] < target) {
11                 if (target >= nums[i] && nums[mid] <= nums[i]) {
12                     j = mid;
13                 } else {
14                     i = mid;
15                 }
16             } else {
17                 if (target <= nums[j] && nums[mid] >= nums[j]) {
18                     i = mid;
19                 } else {
20                     j = mid;
21                 }
22             }
23             
24         }
25         if (nums[i] == target) {
26             return i;
27         }
28         if (nums[j] == target) {
29             return j;
30         }
31         return -1;
32     }
33 }

View Code

这种方法在只有一边出现的时候容易出bug，target > mid 在对比的时候target和mid都统一用num[i]做比较，target < mid 时用num[j]

九章的方式，区分mid在左边还是右边，然后再做判断，合理简单很多，代码如下：

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

View Code

follow up : Search in Rotated Sorted Array II

注意处理重复元素的方法，o(n)

 1 public class Solution {
 2     /** 
 3      * param A : an integer ratated sorted array and duplicates are allowed
 4      * param target :  an integer to be search
 5      * return : a boolean 
 6      */
 7     public boolean search(int[] A, int target) {
 8         if (A == null || A.length == 0) {
 9             return false;
10         }
11         // write your code here
12         int start = 0; 
13         int end = A.length - 1;
14         while (start + 1 < end) {
15             int mid = start + (end - start) / 2;
16             if (A[mid]  == target) {
17                 return true;
18             } else if (A[mid] == A[end]) {
19                 end--;
20             } else if (A[mid] == A[start]){
21                 start++;
22             } else if (A[mid] > A[end]) {
23                 //mid on left
24                 if (target < A[mid] && target >= A[start]) {
25                     end = mid;
26                 } else {
27                     start = mid;
28                 }
29             } else {
30                 //mid on right
31                 if (target >= A[mid] && target <= A[end]) {
32                     start = mid;
33                 } else {
34                     end = mid;
35                 }
36             }
37         }
38         
39         if (A[start] == target) {
40             return true;
41         } else if (A[end] == target){
42             return true;
43         } else {
44             return false;
45         }
46     }
47 }

View Code

2. search in a big sorted array

注意起始点 2^0 = 1, 所以从2^n - 1开始。或者直接从0开始。这道题二分算法，从0开始和从2^n - 1开始不影响整体复杂度。

本题的重点在于用一个lgn的时间找到末尾节点

 1 /**
 2  * Definition of ArrayReader:
 3  * 
 4  * class ArrayReader {
 5  *      // get the number at index, return -1 if index is less than zero.
 6  *      public int get(int index);
 7  * }
 8  */
 9 public class Solution {
10     /**
11      * @param reader: An instance of ArrayReader.
12      * @param target: An integer
13      * @return : An integer which is the index of the target number
14      */
15     public int searchBigSortedArray(ArrayReader reader, int target) {
16         // write your code here
17         int slow = 0;
18         int fast = 1;
19         while (reader.get(2^fast) < target) {
20             fast++;
21             slow++;
22         }
23         
24         
25         int start = 2 ^ slow - 1;
26         int end  = 2 ^ fast;
27         while (start + 1 < end) {
28             int mid = start + (end - start) / 2;
29             if (target > reader.get(mid)) {
30                 start = mid;
31             } else {
32                 end = mid;
33             }
34         }
35         if (reader.get(start) == target) {
36             return start;
37         } else if (reader.get(end) == target) {
38             return end;
39         } else {
40             return -1;
41         }
42     }
43 }

View Code

3. wood cut

Given n pieces of wood with length L[i] (integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. What is the longest length you can get from the n pieces of wood? Given L & k, return the maximum length of the small pieces.

Notice

You couldn't cut wood into float length.

Have you met this question in a real interview?

Yes

Example

For L=[232, 124, 456], k=7, return 114.

二分cut的长度，注意长度从最长的板子的长度开始，而不是从最短的板子长度开始

 1 public class Solution {
 2     /** 
 3      *@param L: Given n pieces of wood with length L[i]
 4      *@param k: An integer
 5      *return: The maximum length of the small pieces.
 6      */
 7     public int woodCut(int[] L, int k) {
 8         // write your code here
 9         int max = Integer.MIN_VALUE;
10         for (int len : L) {
11             max = Math.max(max, len);
12         }
13         int min = 1;
14         while (min + 1 < max) {
15             int mid = min + (max - min) / 2;
16             if (get(L, mid) >= k) {
17                 min = mid;
18             } else {
19                 max = mid;
20             }
21         }
22         if (get(L, max) >= k) {
23             return max;
24         }  else if (get(L, min) >= k) { 
25             return min;
26         }    
27             else {
28             return 0;
29         }
30         
31         
32         
33     }
34     private int get(int[] L, int len) {
35         int count = 0;
36         for (int temp : L) {
37             count += (temp/len);
38         }
39         return count;
40     }
41 }

View Code

4. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

思路：如果中间元素大于其相邻后续元素，则中间元素左侧(包含该中间元素）必包含一个局部最大值。如果中间元素小于其相邻后续元素，则中间元素右侧必包含一个局部最大值。

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

View Code

5. Total Occurrence of Target

二分找到第一个出现的节点和第二个出现的节点

注意，当数组里不存在target value的时候，需要直接返回0

 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 totalOccurrence(int[] A, int target) {
 8         if (A == null || A.length == 0) {
 9             return 0;
10         }
11         // Write your code here
12         int gobalStart, gobalEnd;
13         
14         int start = 0; 
15         int end = A.length - 1;
16         //search for the first index
17         while (start + 1 < end) {
18             int mid = start + (end - start) /2;
19             if (A[mid] >= target) {
20                 end = mid;
21             } else {
22                 start = mid;
23             }
24         }
25         if (A[start] == target) {
26             gobalStart = start;
27         } else if (A[end] == target) {
28             gobalStart = end;
29         } else {
30             return 0;
31         }
32         //gobalStart = A[start] == target ? start : end;
33         //failed for test case : [4], 3
34 
35         
36         
37         //search for second index
38         end = A.length - 1;
39         while (start + 1 < end) {
40             int mid = start + (end - start) / 2;
41             if (A[mid] <= target) {
42                 start = mid;
43             } else {
44                 end = mid;
45             }
46         }
47         gobalEnd = A[end] == target ? end : start;
48         
49         return gobalEnd - gobalStart + 1;
50     }
51 }

View Code

6. K Closest Numbers In Sorted Array

这道题实现起来要注意一些细节

版本1

 1 public class Solution {
 2     /**
 3      * @param A an integer array
 4      * @param target an integer
 5      * @param k a non-negative integer
 6      * @return an integer array
 7      */
 8     public int[] kClosestNumbers(int[] A, int target, int k) {
 9         // Write your code here
10         if (A == null || A.length == 0 || A.length < k) {
11             return null;
12         }
13         int start = 0;
14         int end = A.length - 1;
15         while (start + 1 < end) {
16             int mid = start + (end - start) - 1;
17              if (A[mid] >= target) {
18                 end = mid;
19             } else {
20                 start = mid;
21             }
22         }
23         int left, right;
24         left = start;
25         right = end;
26         
27         ArrayList<Integer> temp = new ArrayList<Integer>(); 
28         for (int i = 0; i < k; i++) {
29             //note : when difference equals add left node first!
30             if (Math.abs(target - A[left]) <= Math.abs(target - A[right])) {
31                 temp.add(A[left]);
32                 if(left > 0) {
33                     left--;
34                 } else {
35                     i++;
36                     while (i < k) {
37                         temp.add(A[right]);
38                         right++;
39                         i++;
40                     }
41                 }
42             } else {
43                 temp.add(A[right]);
44                 if (right < A.length - 1) {
45                     right++;
46                 } else {
47                     i++;
48                     while (i < k) {
49                         temp.add(A[left]);
50                         left--;
51                         i++;
52                     }
53                 }
54             }
55         }
56         int[] ret = new int[temp.size()];
57         for (int i = 0; i < temp.size(); i++)
58         {
59             ret[i] = temp.get(i);
60         }
61         return ret;
62 
63     }
64 }

View Code

其实不需要使用arraylist，因为给了k的size，直接新建一个大小为k的array就好。

另外可以优化一下循环结构体

版本2

用的if continue代替了if else

 1 public class Solution {
 2     /**
 3      * @param A an integer array
 4      * @param target an integer
 5      * @param k a non-negative integer
 6      * @return an integer array
 7      */
 8     public int[] kClosestNumbers(int[] A, int target, int k) {
 9         // Write your code here
10         if (A == null || A.length == 0 || A.length < k) {
11             return null;
12         }
13         int start = 0;
14         int end = A.length - 1;
15         while (start + 1 < end) {
16             int mid = start + (end - start) - 1;
17              if (A[mid] >= target) {
18                 end = mid;
19             } else {
20                 start = mid;
21             }
22         }
23         int left, right;
24         left = start;
25         right = end;
26         
27         int[] temp = new int[k]; 
28         for (int i = 0; i < k; i++) {
29          
30             if (left < 0) {
31                 temp[i] = A[right];
32                 right++;
33                 continue;
34             }
35             if (right >= A.length) {
36                 temp[i] = A[left];
37                 left--;
38                 continue;
39             }
40             
41             //note : when difference equals add left node first!
42             if (Math.abs(target - A[left]) <= Math.abs(target - A[right])) {
43                 temp[i]= A[left];
44                 left--;
45             } else {
46                 temp[i] = A[right];
47                 right++;
48             }
49         }
50         return temp;
51     }
52 }

View Code

7. Find Minimum in Rotated Sorted Array II

对于1111111111101的极端情况只能用0(n)的方法解

 1 public class Solution {
 2     /**
 3      * @param num: a rotated sorted array
 4      * @return: the minimum number in the array
 5      */
 6     public int findMin(int[] num) {
 7         if (num == null || num.length == 0) {
 8             return 0;
 9         }
10         int start = 0;
11         int end = num.length - 1;
12         while (start + 1 < end) {
13             int mid = start + (end - start) / 2;
14             // on left part 
15             if (num[mid] == num[end]) {
16                 //用于解决11111111111111111101的情况
17                 end--;
18             }
19             else if (num[mid] >= num[end]) {
20                 start = mid;
21             } else {
22                 end = mid;
23             }
24         }
25         return Math.min(num[start], num[end]);    
26         
27     }
28 }

View Code

8. search a 2d matrix

注意在横向是递增的，在垂直方向是从小到大递增的特性

 1 public class Solution {
 2     /**
 3      * @param matrix: A list of lists of integers
 4      * @param: A number you want to search in the matrix
 5      * @return: An integer indicate the occurrence of target in the given matrix
 6      */
 7     public int searchMatrix(int[][] matrix, int target) {
 8         // write your code here
 9         if (matrix == null || matrix.length == 0) {
10             return 0;
11         }
12 
13         int m = matrix[0].length;
14         int n = matrix.length;
15         int x, y;
16         int count = 0;
17         x = n - 1;
18         y = 0;
19         while (x >= 0  && y <= m -1) {
20             if (matrix[x][y] == target) {
21                 count++;
22                 x--;
23             } else if (matrix[x][y] < target) {
24                 y++;
25             } else {
26                 x--;
27             }
28             
29         }
30         return count;
31     }
32 }

View Code