需要牢记的二分法基础模板
2022-03-23 本文已影响0人
奋斗的韭菜汪
public class BasicBinarySearch {
public static void main(String[] args) {
int[] nums = {1,3,5,7,10,13,18};
System.out.println("数字所在位置:" + searchNum(nums, 18));
}
private static int searchNum(int[] nums, int target) {
if (nums == null || nums.length == 0){
return -1;
}
int start = 0;
int end = nums.length -1;
int middle;
//记住这里,为什么不用start<=end而用start + 1 < end,因为start + (end-start)/2会取不到最左边的数18
while (start + 1 < end){
middle = start + (end-start)/2;
if (target < nums[middle]){
end = middle;
} else if (target > nums[middle]){
start = middle;
} else {
return middle;
}
}
if (target == nums[start]) {
return start;
} else if (target == nums[end]) {
return end;
} else {
return -1;
}
}
}
搜索旋转排序数组
click here for leetcode detail
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0){
return -1;
}
int start = 0;
int end = nums.length - 1;
int middle;
while (start + 1 < end){
middle = start + (end -start)/2;
if (nums[middle] == target){
return middle;
}
//解题思路:不管怎么旋转,都可以把nums看成前后递增的两端,只用通过nums[middle]
//和nums[start]就可以判断target是在二分的前半部分还是后半部分。
//这里需要注意
if (nums[middle] > nums[start]){
//这里需要注意
if (target <= nums[middle] && target >= nums[start]){
end = middle;
} else {
start = middle;
}
} else {
if ( target >= nums[middle] && target <= nums[end]){
start = middle;
} else {
end = middle;
}
}
}
if(nums[start] == target){
return start;
}
if(nums[end] == target){
return end;
}
return -1;
}
}
找旋转排序数组中的最小值
click here for leetcode detail
class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0){
return -1;
}
int start = 0;
int end = nums.length - 1;
int mid = -1;
while(start + 1 < end){
mid = start + (end - start)/2;
if (nums[mid] > nums[end]){
start = mid;
} else {
end = mid;
}
}
return nums[start] < nums[end] ? nums[start] : nums[end];
}
}
寻找峰值
click here for leetcode detail
class Solution {
public int findPeakElement(int[] nums) {
if ( nums == null || nums.length < 2){
return 0;
}
int start = 0;
int end = nums.length - 1;
int mid;
while(start + 1 < end){
mid = start + (end - start)/2;
//下峰
if (nums[mid] < nums[mid -1]){
end = mid;
//上峰
} else if (nums[mid] < nums[mid + 1]){
start = mid;
} else {
return mid;
}
}
return nums[start] > nums[end] ? start : end;
}
}