给定已按升序排列的n个元素A[0:n-1],现要在这n个元素中找出某一特定元素key,采用二分搜索算法实现
时间: 2023-05-12 11:03:51 浏览: 37
好的,这是一个经典的二分搜索问题。我们可以通过以下步骤实现:
1. 初始化左右边界,left = 0, right = n-1。
2. 当 left <= right 时,执行以下步骤:
a. 计算中间位置 mid = (left + right) // 2。
b. 如果 A[mid] == key,则返回 mid。
c. 如果 A[mid] > key,则在左半部分继续搜索,更新 right = mid - 1。
d. 如果 A[mid] < key,则在右半部分继续搜索,更新 left = mid + 1。
3. 如果没有找到 key,则返回 -1。
下面是 Python 代码实现:
def binary_search(A, key):
left, right = 0, len(A)-1
while left <= right:
mid = (left + right) // 2
if A[mid] == key:
return mid
elif A[mid] > key:
right = mid - 1
else:
left = mid + 1
return -1
如果 A 中存在 key,则该函数返回 key 在 A 中的下标,否则返回 -1。
相关问题
给定已按升序排列的n个元素A[0:n-1],现要在这n个元素中找出某一特定元素key,采用二分搜索算法实现。
可以使用以下代码实现二分搜索算法:
```
int binarySearch(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
```
其中,arr是已按升序排列的n个元素,left和right分别是数组的左右边界,key是要查找的特定元素。函数返回key在数组中的下标,如果不存在则返回-1。
例如,如果要在数组arr中查找元素key=5,可以调用函数binarySearch(arr, 0, n-1, 5),其中n是数组的长度。如果函数返回值为2,则表示key在数组中的下标为2。
Java实现给定已按升序排列的n个元素A[0:n-1],现要在这n个元素中找出某一特定元素key,采用二分搜索算法实现
可以使用以下代码实现:
public static int binarySearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] < key) {
low = mid + 1;
} else if (arr[mid] > key) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
其中,arr是已按升序排列的n个元素,key是要查找的特定元素。如果找到了该元素,则返回其下标;否则返回-1。