用c++实现一个二分查找算法
时间: 2023-05-15 09:05:53 浏览: 70
二分查找算法的实现如下:
```c
int binary_search(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
其中,arr 是一个已经排好序的数组,n 是数组的长度,target 是要查找的目标值。函数返回目标值在数组中的下标,如果目标值不存在,则返回 -1。
注意,这个算法只适用于已经排好序的数组。
相关问题
用c++写一个二分查找算法
当然可以,以下是一个简单的二分查找算法的 C 代码:
```
int binary_search(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
其中,`arr` 是一个已经排好序的数组,`n` 是数组的长度,`target` 是要查找的目标值。函数返回目标值在数组中的下标,如果目标值不存在,则返回 -1。
希望这个代码能够帮到你!
用C++编写一个实现二分查找的算法
以下是 C++ 实现二分查找的代码示例:
```C++
int binary_search(vector<int> arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
该函数接受一个有序数组 `arr` 和目标元素 `target`,返回目标元素在数组中的下标,如果不存在则返回 -1。
算法的核心部分是循环内的判断,如果当前中间元素等于目标元素,则直接返回下标;如果中间元素小于目标元素,则在右半部分继续查找;否则在左半部分查找。由于每次查找都将目标区间缩小一半,因此时间复杂度为 O(log n)。
注意:该函数的参数 `vector<int> arr` 表示使用了 C++ 中的标准库 `vector` 来存储数组。如果使用原始数组,则需要传递数组的指针和长度作为参数。