二分搜索非递归算法c语言

下面是二分搜索的非递归算法实现：

int binarySearch(int arr[], int left, int right, int x) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] < x)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

其中，`arr`为待搜索的数组，`left`和`right`分别为搜索区间的左右边界，`x`为待搜索的值。函数返回`x`在数组中的下标，如果不存在，则返回-1。

相关问题

C语言二分查找非递归

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语言实现折半查找的递归和非递归算法

折半查找，也称二分查找，是一种基于比较的查找算法。它的时间复杂度为 O(log n)，适用于有序的线性结构（如数组、有序列表等）。

非递归算法实现折半查找：

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;
}

递归算法实现折半查找：

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 循环实现，递归算法使用函数递归实现。