二分查找数据结构代码
时间: 2024-05-28 19:07:59 浏览: 23
二分查找是一种常用的查找算法,也称为折半查找。它的基本思想是,通过比较中间位置元素和目标值的大小关系,每次可以将查找范围缩小一半,直到找到目标元素或者查找范围为空为止。以下是一份 C++ 实现的二分查找代码:
```
int binarySearch(int arr[], int left, int right, int target) {
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`、查找范围左边界 `left`、右边界 `right` 和目标值 `target`,并返回目标值在数组中的下标(如果存在),否则返回 -1。
相关问题
数据结构二分查找算法代码
二分查找是一种基于比较目标值和数组中间元素的查找算法。在每次比较后,将查找范围缩小到数组的一半,直到找到目标值或者查找范围为空。
以下是二分查找算法的代码实现:
```c++
int binarySearch(int arr[], int left, int right, int target) {
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是待查找的有序数组,left和right是查找范围的左右边界,target是目标值。
数据结构c语言二分查找代码
以下是C语言中实现二分查找的代码示例:
1. 递归实现二分查找:
```c
int binarySearchRecursive(int arr[], int low, int high, int target) {
if (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] > target) {
return binarySearchRecursive(arr, low, mid - 1, target);
}
else {
return binarySearchRecursive(arr, mid + 1, high, target);
}
}
return -1; // 如果未找到目标元素,返回-1
}
```
2. 非递归实现二分查找:
```c
int binarySearchIterative(int arr[], int low, int high, int target) {
while (low <= high) {
int mid = low + (high - low / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] > target) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return -1; // 如果未找到目标元素,返回-1
}
```
这两种方法都是基于有序数组进行二分查找。递归实现通过不断缩小查找范围来找到目标元素,而非递归实现则使用循环来实现相同的功能。