用折半查找的方法进行一组数据的查找。若找到输出其位置,找不到输出无此元素。
时间: 2024-03-01 21:54:33 浏览: 3
折半查找也叫二分查找,是一种效率较高的查找算法,其主要思想是将待查找的区间不断二分,缩小查找范围,直到找到目标元素或者确定目标元素不存在为止。
具体的实现步骤如下:
1. 定义左右两个指针,分别指向区间的起点和终点;
2. 计算中间元素的下标mid,如果中间元素等于目标元素,则直接返回mid;
3. 如果中间元素大于目标元素,则在左半区间继续查找,将右指针移动到mid-1的位置;
4. 如果中间元素小于目标元素,则在右半区间继续查找,将左指针移动到mid+1的位置;
5. 如果左指针大于右指针,则说明该区间内不存在目标元素,返回“无此元素”。
下面是一个示例代码:
```
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) { // 注意这里是 "<=",因为可能存在left=right的情况
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1; // 返回-1表示无此元素
}
```
其中,arr为待查找的数组,n为数组的长度,target为目标元素的值。如果找到了目标元素,则返回它在数组中的下标;否则返回-1。
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)