<分区>
我总是对二分搜索算法的条件感到困惑,这让我在编程竞赛中花费了很多时间。我的问题是何时使用这些条件?
1. while (low < high)
2. while (high - low > 1)
3. while (low <= high)
low
= 解决方案集中的最低值。
high
= 解决方案集中的最大值。
标签 java c++ binary-search
<分区>
我总是对二分搜索算法的条件感到困惑,这让我在编程竞赛中花费了很多时间。我的问题是何时使用这些条件?
1. while (low < high)
2. while (high - low > 1)
3. while (low <= high)
low
= 解决方案集中的最低值。
high
= 解决方案集中的最大值。
最佳答案
while (low < high)
在搜索范围 [low, high)
时使用.更新时 high
, 使用 high = mid
.更新时 low
, 使用 low = mid + 1
.while (high - low > 1)
在搜索范围 (low, high)
时使用.更新时 high
, 使用 high = mid
.更新时 low
, 使用 low = mid
.while (low <= high)
在搜索范围 [low, high]
时使用.更新时 high
, 使用 high = mid - 1
.更新时 low
, 使用 low = mid + 1
.代码如下:
public class BinarySearch {
public static void main(String[] args) {
Integer[] nums = { 4, 9, 12, 18, 20, 26, 28, 29, 55 };
for (int i = 0; i < nums.length; ++i) {
System.out.println(binarySearch1(nums, nums[i]));
System.out.println(binarySearch2(nums, nums[i]));
System.out.println(binarySearch3(nums, nums[i]));
}
}
public static <T extends Comparable<T>> int binarySearch1(T[] array, T value) {
final int NOT_FOUND = -1;
int low = 0;
int high = array.length;
while (low < high) {
int mid = low + (high - low) / 2;
int comparison = array[mid].compareTo(value);
if (comparison == 0) {
return mid;
} else if (comparison > 0) {
high = mid;
} else {
low = mid + 1;
}
}
return NOT_FOUND;
}
public static <T extends Comparable<T>> int binarySearch2(T[] array, T value) {
final int NOT_FOUND = -1;
int low = -1;
int high = array.length;
while (high - low > 1) {
int mid = low + (high - low) / 2;
int comparison = array[mid].compareTo(value);
if (comparison == 0) {
return mid;
} else if (comparison > 0) {
high = mid;
} else {
low = mid;
}
}
return NOT_FOUND;
}
public static <T extends Comparable<T>> int binarySearch3(T[] array, T value) {
final int NOT_FOUND = -1;
int low = 0;
int high = array.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int comparison = array[mid].compareTo(value);
if (comparison == 0) {
return mid;
} else if (comparison > 0) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return NOT_FOUND;
}
}
关于java - 二分查找条件,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30928268/