实现有序数组的二分查找。
时间: 2023-10-27 19:05:17 浏览: 37
二分查找,也称折半查找,是一种基于比较目标值和数组中间元素的搜索算法。若目标值等于中间元素,则找到目标值;若目标值较小,则在数组的左半部分继续查找;若目标值较大,则在数组的右半部分继续查找。重复以上步骤直到找到目标值或者确定目标值不存在为止。
以下是一个实现有序数组的二分查找的示例代码,假设要查找的目标值为`target`,有序数组为`nums`:
```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
```
在上述代码中,我们首先初始化左右指针`left`和`right`分别为数组的首尾下标,然后在循环中不断缩小查找范围,直到左指针大于右指针为止。在每次循环中,我们计算中间元素的下标`mid`,如果中间元素等于目标值,则返回其下标;否则,如果中间元素较小,则将左指针移动到`mid+1`的位置;否则,将右指针移动到`mid-1`的位置。如果循环结束时仍然没有找到目标值,则返回-1表示目标值不存在于数组中。
相关问题
实现对有序数组二分查找
二分查找是一种高效的查找算法,适用于有序数组。它通过将数组分成两部分,并与目标值进行比较,从而确定目标值在哪一部分中。以下是实现有序数组二分查找的步骤:
1. 初始化左指针left为数组的起始位置,右指针right为数组的结束位置。
2. 计算中间位置mid,可以使用公式mid = (left + right) / 2。
3. 比较中间位置的元素与目标值的大小:
- 如果中间位置的元素等于目标值,则找到了目标值,返回中间位置。
- 如果中间位置的元素大于目标值,则目标值可能在左半部分,更新右指针right为mid - 1。
- 如果中间位置的元素小于目标值,则目标值可能在右半部分,更新左指针left为mid + 1。
4. 重复步骤2和步骤3,直到找到目标值或者左指针大于右指针。
如果找到了目标值,返回其索引;如果没有找到,返回-1表示未找到。
有序数组的二分查找算法的实现
二分查找是一种基于比较的查找算法,适用于有序数组。实现步骤大致如下:
1. 定义两个指针,一个指向数组的起始位置,一个指向数组的末尾位置。
2. 计算数组的中间位置,即 mid = (left + right) / 2。
3. 用中间位置的值与需要查找的值进行比较。
a. 如果中间值等于查找值,则查找成功,返回中间位置。
b. 如果中间值大于查找值,则说明需要查找的值在左半部分,将右指针移动到 mid -1 处。
c. 如果中间值小于查找值,则说明需要查找的值在右半部分,将左指针移动到 mid + 1 处。
4. 重复步骤2~3直到找到需要查找的值或者左指针大于右指针,查找失败。
下面是二分查找算法的 C++ 代码实现:
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] > target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return -1;
}
其中,arr[] 表示需要查找的数组,left 和 right 分别表示数组的起始位置和末尾位置,target 表示需要查找的目标值。如果查找成功,返回目标值在数组中的索引位置,否则返回 -1。