什么是二分查找?如何实现?
时间: 2023-12-26 16:03:53 浏览: 32
二分查找是一种常见的查找算法,也被称为折半查找。它基于比较的思想,将一个有序数组的查找范围逐渐缩小,最终找到目标元素的位置。实现过程通常包括以下步骤:
1. 确定查找范围,即数组的左右边界;
2. 计算数组的中间位置;
3. 如果中间位置的数值等于目标值,则查找成功,返回其位置;
4. 如果中间位置的数值小于目标值,则目标值在右半部分,更新左边界;
5. 如果中间位置的数值大于目标值,则目标值在左半部分,更新右边界;
6. 重复2-5步,直到查找成功或者范围缩小到空。
实现时可以使用递归或者循环的方式,复杂度为O(log(n))。
相关问题
请问什么是二分查找?
二分查找是一种在有序数组中查找特定元素的搜索算法。该算法通过将目标值与数组的中间元素进行比较,如果两者相等,则返回中间元素的索引。如果目标值较小,则继续在左侧子数组中查找;如果目标值较大,则继续在右侧子数组中查找。通过不断缩小搜索范围,最终可以找到目标元素或确定其不存在于数组中。
以下是Java实现二分查找的代码示例:
```java
public static int binarySearch(int[] array, int target) {
int left = 0, right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) {
return mid;
} else if (array[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
1. 什么是二分查找算法?如何实现?python实现
二分查找算法是一种基于比较目标值和数组中间元素的高效搜索算法。该算法要求待查找的数组必须是有序的。
二分查找的基本思路是将待查找区间不断地缩小为原来的一半,直到找到目标值或者区间为空。
具体实现过程如下:
1. 初始化待查找区间的左右边界,即 left=0,right=len(nums)-1。
2. 循环判断,直到待查找区间为空为止。
3. 计算中间位置 mid=(left+right)//2。
4. 如果目标值等于中间位置的值 nums[mid],则直接返回 mid。
5. 如果目标值小于中间位置的值 nums[mid],则将待查找区间缩小为左半部分,即 right=mid-1。
6. 如果目标值大于中间位置的值 nums[mid],则将待查找区间缩小为右半部分,即 left=mid+1。
7. 循环结束后,如果没有找到目标值,则返回 -1。
下面是 Python 实现:
```python
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
其中,nums 是待查找的有序数组,target 是目标值。该函数返回目标值在数组中的索引值,如果没有找到则返回 -1。