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那就判断条件时先start >或< target再end >或< target。统一格式，判定条件，start + 1 < end， start和end都是mid，循环完之后，
//根据具体条件看是start开始还是end开始。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 比前一个小，二分法
// 45678123,中点和end进行比较！！！比end大，范围所小到mid，end
// 78123456,中点和end进行比较！！！比end小，范围缩小到start，mid
//最后在节点start和end缩小到前后两个时候，比较前后的大小，谁小输出结果就是谁
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
// 针对rotated这类问题。想象在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
