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

這種方法在只有一邊出現(xiàn)的時(shí)候容易出bug，target > mid 在對(duì)比的時(shí)候target和mid都統(tǒng)一用num[i]做比較，target < mid 時(shí)用num[j]

九章的方式，區(qū)分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?

注意處理重復(fù)元素的方法，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

注意 起始點(diǎn) 2^0 = 1, 所以從2^n - 1開始。 或者直接從0開始。這道題二分算法，從0開始和從2^n - 1開始不影響整體復(fù)雜度。

本題的重點(diǎn)在于用一個(gè)lgn的時(shí)間找到末尾節(jié)點(diǎn)

?

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.

思路：如果中間元素大于其相鄰后續(xù)元素，則中間元素左側(cè)(包含該中間元素）必包含一個(gè)局部最大值。如果中間元素小于其相鄰后續(xù)元素，則中間元素右側(cè)必包含一個(gè)局部最大值。

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

二分找到第一個(gè)出現(xiàn)的節(jié)點(diǎn)和第二個(gè)出現(xiàn)的節(jié)點(diǎn) 注意，當(dāng)數(shù)組里不存在target value的時(shí)候，需要直接返回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

這道題實(shí)現(xiàn)起來要注意一些細(xì)節(jié) 版本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

其實(shí)不需要使用arraylist，因?yàn)榻o了k的size，直接新建一個(gè)大小為k的array就好。

另外可以優(yōu)化一下循環(huán)結(jié)構(gòu)體

版本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

對(duì)于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

?

轉(zhuǎn)載于:https://www.cnblogs.com/jiangchen/p/5875846.html

總結(jié)

以上是生活随笔為你收集整理的binary search完整笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。