LC34. Find First and Last Position of Element in Sorted Array
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
public int[] searchRange(int[] nums, int target) {
int[] res = {-1, -1};
if (nums.length == 0 || nums == null) return res;
int start = 0, end = nums.length - 1;
while (start + 1 < end){
int mid = start + (end - start) / 2;
if (nums[mid] == target) end = mid;
else if (nums[mid] > target) end = mid;
else start = mid;
}
if (nums[start] == target) res[0] = start;
else if (nums[end] == target) res[0] = end;
else res[0] = -1;
start = 0;
end = nums.length - 1;
while (start + 1 < end){
int mid = start + (end - start) / 2;
if (nums[mid] == target) start = mid;
else if (nums[mid] > target) end = mid;
else start = mid;
}
if (nums[end] == target) res[1] = end;
else if (nums[start] == target) res[1] = start;
else res[1] = -1;
return res;
}
LC35. Search Insert Position
Input: [1,3,5,6], 5
Output: 2
public int searchInsert(int[] nums, int target) {
if (target < nums[0]) return 0;
//find the first element which >= target int the array
// first element 先比較start西篓， last element比較end
int start = 0, end = nums.length - 1;
while (start + 1 < end){
int mid = start + (end - start) / 2;
if (nums[mid] == target){
return mid;
} else if (nums[mid] > target){
end = mid;
} else {
start = mid;
}
}
if (nums[start] >= target) return start;
else if (nums[end] >= target) return end;
else return end + 1;
}
LC74. Search a 2D Matrix
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
//二分查找法的解題步驟莹弊，先看題目要求是求first position of element >或< target,還是
//last position of element >或< target.如果是first那就判斷條件時(shí)先start >或< target再end >或< target谒拴。統(tǒng)一格式捐迫，判定條件泳叠，start + 1 < end吼过， start和end都是mid城菊，循環(huán)完之后谊路，
//根據(jù)具體條件看是start開(kāi)始還是end開(kāi)始传于。O(logn + logm)
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) return false;
if (matrix[0] == null || matrix[0].length == 0) return false;
// last of position <= target;
int m = matrix.length;
int row = 0;
int start = 0, end = m - 1;
while (start + 1 < end){
int mid = start + (end - start) / 2;
if (matrix[mid][0] == target) return true;
else if (matrix[mid][0] < target) start = mid;
else end = mid;
}
if(matrix[end][0] <= target) row = end;
else if (matrix[start][0] <= target) row = start;
start = 0;
end = matrix[row].length - 1;
while (start + 1 < end){
int mid = start + (end - start) / 2;
if (matrix[row][mid] == target) return true;
else if (matrix[row][mid] < target) start = mid;
else end = mid;
}
if (matrix[row][start] == target) return true;
else if (matrix[row][end] == target) return true;
else return false;
}
- Search a 2D Matrix II
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.
//We start search the matrix from top right corner, initialize the current position to top right corner, if the target is greater than the value in current position, then the target can not be in entire row of current position because the row is sorted, if the target is less than the value in current position, then the target can not in the entire column because the column is sorted too. We can rule out one row or one column each time, so the time complexity is O(m+n).
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
int col = matrix[0].length - 1;
int row = 0;
while (col >= 0 && row <=matrix.length - 1){
if (matrix[row][col] == target) return true;
else if (matrix[row][col] > target) col--;
else row++;
}
return false;
}
LC162. Find Peak Element
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.
public int findPeakElement(int[] nums) {
if (nums.length == 0 || nums == null) return 0;
int start = 0, end = nums.length - 1;
while (start + 1 < end){
int mid = start + (end - start)/2;
if (nums[mid] < nums[mid-1]){
end = mid;
} else if (nums[mid] < nums[mid + 1]){
start = mid;
} else {
end = mid;
}
}
return nums[start] < nums[end] ? end : start;
}
LC153. Find Minimum in Rotated Sorted Array
Input: [3,4,5,1,2]
Output: 1
// first postion 比前一個(gè)小囱挑，二分法
// 45678123,中點(diǎn)和end進(jìn)行比較！Ｕ恿铩平挑！比end大，范圍所小到mid系草，end
// 78123456,中點(diǎn)和end進(jìn)行比較Ｍㄏā！找都！比end小唇辨，范圍縮小到start，mid
//最后在節(jié)點(diǎn)start和end縮小到前后兩個(gè)時(shí)候能耻，比較前后的大小赏枚，誰(shuí)小輸出結(jié)果就是誰(shuí)
public int findMin(int[] nums) {
int start = 0, end = nums.length - 1;
while (start + 1 < end){
int mid = start + (end - start)/2;
if (nums[mid] > nums[end]){
start = mid;
} else {
end = mid;
}
}
if (nums[start] < nums[end]) return nums[start];
else return nums[end];
}
LC33. Search in Rotated Sorted Array
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
// 針對(duì)rotated這類問(wèn)題亡驰。想象在14象限的兩條直線。
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int start = 0, end = nums.length - 1;
while (start + 1 < end){
int mid = start + (end - start)/2;
if (nums[mid] == target) return mid;
if (nums[mid] > nums[start]){
if(target < nums[mid] && target >= nums[start]){
end = mid;
} else {
start = mid;
}
} else if (nums[mid] < nums[end]){
if (target <= nums[end] && target > nums[mid]){
start = mid;
} else {
end = mid;
}
}
}
if (nums[start] == target) return start;
else if (nums[end] == target) return end;
return -1;
}
LC4. Median of Two Sorted Arrays
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
