请写出二分查找的设计思想或相应的函数代码
时间: 2023-12-09 17:03:50 浏览: 26
二分查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。其基本思想是将数组分成两部分,通过比较中间元素和目标元素的大小关系,确定下一步查找的方向,直到找到目标元素或确定不存在该元素为止。
二分查找的时间复杂度为 O(log n),是一种高效的查找算法。
以下是二分查找的函数代码实现:
```
int binarySearch(int arr[], int left, int right, int x) {
if (right >= left) {
int mid = left + (right - left) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, left, mid - 1, x);
return binarySearch(arr, mid + 1, right, x);
}
return -1;
}
```
其中,arr 表示要查找的有序数组,left 和 right 分别表示数组的左右边界,x 表示要查找的元素。首先判断 right 是否大于等于 left,若成立,则求出中间位置 mid,如果 arr[mid] 等于 x,则找到了目标元素,返回 mid;如果 arr[mid] 大于 x,则在左半部分继续查找,即递归调用函数 binarySearch(arr, left, mid - 1, x);如果 arr[mid] 小于 x,则在右半部分继续查找,即递归调用函数 binarySearch(arr, mid + 1, right, x)。若最终未查找到目标元素,则返回 -1。