
luckydog
V1
2022/03/11阅读:36主题:默认主题
***Code 34
再探二分查找
之前在code_33里对二分查找有了一点理解,当时理解的点在于while循环中的if涉及的区间问题,简简单单理解为>,<,=的三个if并集为全集就行了,现在看来想法未免有点幼稚。
三种问题
不妨假设一个数组 nums = [1, 2, 3, 3, 3, 4], target = 3
寻找target
寻找第一个target
寻找最后一个target
问题一
写法一
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return -1;
}
写法二
public static int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return -1;
}
两种写法的区别
1. 初始化left,right不同 2. while的判断不同 先明确一点,left,right的初始化值表示了搜索区间
写法一表示的搜索区间为[left, right],写法二的搜索区间为[left, right),正是由于搜索区间的不同导致了while判断时候的不同,因为方法一退出while的条件是left = right + 1, 方法二的退出条件是left = right,
-
while退出时方法一的搜索区间可表示为[right + 1, right] while退出时方法二的搜索区间可表示为[right, right)
此时两个搜索区间都为空,表示所有元素已经被搜索,因此两种写法都可以
问题二
写法一
public static int leftBinarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 退出时left = right + 1,
// 因此left范围为[0, nums.length]
// 同理right范围为[-1, nums.length-1]
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
//相等时右侧向左逼近,left停止在target,right停在target前一个
right = mid - 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
//小于的话left还要再加1,因此left停止在target
left = mid + 1;
}
}
//nums[left] != target 表示在left停在数组中间没找到
//left >= nums.length 表示整个数组都小于target
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
问题三
写法一
public static int rightBinarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 退出时left = right + 1,
// 因此left范围为[0, nums.length]
// 同理right范围为[-1, nums.length-1]
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
//相等时右侧向右逼近,left停止在target后一个,right停在target
left = mid + 1;
} else if (nums[mid] > target) {
//小于的话right还要再减1,因此right停在target
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
//nums[left] != target 表示在right停在数组中间没找到
//right < 0表示整个数组都大于target
if (right < 0 || nums[left] != target) {
return -1;
}
return right;
}
作者介绍

luckydog
V1