有15个已经排好序的整数存放在一个数组中,输入1个整数,要求用二分查找法找出该数是数组中第几个元素的值。如果该数不在数组中,则输出无此数。
时间: 2023-07-16 19:16:26 浏览: 97
二分查找是一种高效的查找算法,可以在有序数组中快速查找指定的元素。下面是使用二分查找算法在一个已经排好序的整数数组中查找指定元素的代码实现:
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 示例:在一个排好序的数组中查找指定元素
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]
target = 15
index = binary_search(arr, target)
if index == -1:
print("无此数")
else:
print("该数是数组中第{}个元素的值".format(index + 1))
```
在这里,我们首先定义了一个 `binary_search` 函数,该函数接受两个参数:一个已经排好序的整数数组和要查找的目标元素。函数使用 `left` 和 `right` 两个指针指向数组的左右两端,然后在一个循环中不断地缩小查找范围,直到找到目标元素或者确定目标元素不存在为止。
具体来说,每次循环中,我们计算出中间元素的索引,并将其保存在 `mid` 变量中。然后,我们比较中间元素和目标元素的大小关系,如果中间元素等于目标元素,那么我们就找到了目标元素,直接返回它在数组中的索引。如果中间元素小于目标元素,那么目标元素一定在中间元素的右侧,因此将左指针移动到 `mid + 1` 的位置。如果中间元素大于目标元素,那么目标元素一定在中间元素的左侧,因此将右指针移动到 `mid - 1` 的位置。不断重复这个过程,直到找到目标元素或者确定目标元素不存在为止。
最后,我们在主程序中定义了一个已经排好序的整数数组 `arr` 和要查找的目标元素 `target`。然后,我们调用 `binary_search` 函数查找目标元素在数组中的位置,如果目标元素不存在,则输出 "无此数",否则输出目标元素在数组中的位置。在这个例子中,目标元素 `15` 在数组中的位置是第 8 个元素,因此程序输出 "该数是数组中第8个元素的值"。
阅读全文