什么是binary search
时间: 2023-07-03 07:03:32 浏览: 48
二分查找(Binary Search),也称折半查找,是一种在有序数组中查找特定元素的搜索算法。它的思想是将数组分成两半,判断要查找的元素在哪一半中,然后递归地在相应的半边中查找,直到找到该元素或者确定该元素不存在于数组中。二分查找的时间复杂度为 O(log n)。由于它的高效性和简单性,在很多编程语言的标准库中都有实现。
相关问题
binarySearch
二分查找(Binary Search),也叫折半查找,是一种在有序数组中查找目标值的算法。基本思想是将已经排序的数组分成两部分,通过比较目标值和中间值,不断缩小查找范围,最终找到目标值。
具体来说,二分查找的过程如下:
1. 取数组的中间元素,比较它和目标值的大小。
2. 如果中间元素等于目标值,则查找成功,返回该元素的下标。
3. 如果中间元素大于目标值,则在数组左半部分继续查找。
4. 如果中间元素小于目标值,则在数组右半部分继续查找。
5. 重复以上步骤,直到找到目标值或者查找范围为空。
需要注意的是,二分查找要求数组是有序的,否则无法保证查找结果的正确性。此外,如果数组中包含多个相同的目标值,二分查找可能会返回其中任意一个下标,具体返回哪一个下标取决于实现方式和查找顺序。
java的Arrays是binarySearch是?
在 Java 中,`Arrays.binarySearch()` 是一个用于在已排序的数组中执行二分查找的方法。它接受三个参数:要进行查找的数组,要查找的值,以及可选的比较器(Comparator)。
该方法返回要查找的值在数组中的索引,如果找到则返回非负值;如果未找到,则返回一个负值。返回的负值是根据要查找的值在数组中应该插入的位置来计算的,具体计算方式为:返回值 = -(插入点) - 1。
需要注意的是,`binarySearch()` 方法只能在已排序的数组上进行有效操作。如果在未排序的数组上使用该方法,结果将是不确定的。
以下是一个使用 `binarySearch()` 方法的示例:
```java
int[] arr = {1, 3, 5, 7, 9};
int index = Arrays.binarySearch(arr, 5);
if (index >= 0) {
System.out.println("找到了,索引为:" + index);
} else {
System.out.println("未找到,应插入的位置为:" + (-index - 1));
}
```
输出结果:
```
找到了,索引为:2
```
注意:在使用 `binarySearch()` 方法之前,必须确保数组已经按照预期顺序进行了排序。