C语言二分查找非递归
时间: 2023-11-15 07:00:43 浏览: 67
C语言二分查找非递归是一种查找算法,它可以在有序数组中快速查找指定元素的位置。其基本思想是将数组分成两部分,判断要查找的元素在哪一部分中,然后再在该部分中继续进行二分查找,直到找到该元素或者确定该元素不存在为止。下面是C语言二分查找非递归的代码实现:
int binarySearch(int arr[], int len, int key) {
int low = 0, high = len - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
其中,arr为有序数组,len为数组长度,key为要查找的元素。在函数中,首先定义了low和high两个变量,分别表示数组的左右边界。然后,使用while循环进行二分查找,每次将数组分成两部分,判断要查找的元素在哪一部分中,然后再在该部分中继续进行二分查找,直到找到该元素或者确定该元素不存在为止。如果找到该元素,则返回该元素的下标;否则,返回-1表示该元素不存在。
相关问题
二分查找递归和非递归c语言代码
递归实现二分查找的C语言代码:
```
int binarySearch(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 binarySearch(arr, low, mid - 1, target);
}
else {
return binarySearch(arr, mid + 1, high, target);
}
}
return -1;
}
```
非递归实现二分查找的C语言代码:
```
int binarySearch(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;
}
```
C语言实现折半查找的递归和非递归算法
折半查找,也称二分查找,是一种基于比较的查找算法。它的时间复杂度为 O(log n),适用于有序的线性结构(如数组、有序列表等)。
非递归算法实现折半查找:
```c
int binary_search(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
递归算法实现折半查找:
```c
int binary_search(int arr[], int left, int right, int target) {
if (left <= right) {
int mid = (left + right) >> 1;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binary_search(arr, mid + 1, right, target);
} else {
return binary_search(arr, left, mid - 1, target);
}
}
return -1;
}
```
其中,arr 为有序数组,n 表示数组长度,target 表示要查找的值。非递归算法使用 while 循环实现,递归算法使用函数递归实现。