写出二分法查找的代码(arr为按升序排列的数组,key为待查找的元素,n为数组长度,返回值为key所在的元素的下标,未找到返回-1)(搜索算法)备注:int binary_search(int *arr, int key, int n)
时间: 2024-03-28 21:41:28 浏览: 21
好的,这是二分查找的代码实现:
```
int binary_search(int *arr, int key, int n) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
二分法查找是一种高效的查找算法,它的时间复杂度为O(logn)。在每次比较的时候,都可以将查找区间缩小一半,直到找到或者区间为空。
相关问题
函数为二分法查找key值。数组中元素已递增排序,若找到key则返回对应的下标,否则返回-1。
好的,这是一个关于算法的问题,我能为您解答。以下是二分查找的实现方式:
```
int binarySearch(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
其中,参数 `arr` 是已经排好序的数组,`left` 和 `right` 是对应要查找的范围,`key` 是要查找的值。函数会不断取数组中间的值进行比较,缩小查找的范围,直到找到该值或者范围缩小到无法查找为止。如果找到了,则返回对应的下标,否则返回 -1。
二分法插入 void BiInsertion(int a[],int n,int type)输入乱序的数组,通过二分法排序算法将其按升序排列。 预期输入:321
好的,这是一个经典的排序问题。我可以给你一个简单的二分法插入排序算法,可以将输入的乱序数组按升序排列。具体步骤如下:
1. 首先,定义一个函数 BiInsertion,它接受一个数组 a,数组长度 n 和排序类型 type(1 表示升序,-1 表示降序)作为输入参数。
2. 然后,从数组的第二个元素开始,依次将每个元素插入到已排好序的子数组中。
3. 对于第 i 个元素,使用二分查找在已排好序的子数组中找到它应该插入的位置 j。
4. 然后,将第 i 个元素插入到位置 j 上,并将位置 j 及之后的元素依次后移一位。
5. 最后,将第 i 个元素插入到位置 j 上,完成第 i 轮插入排序。
下面是代码实现:
```
void BiInsertion(int a[], int n, int type) {
for (int i = 1; i < n; i++) {
int left = 0, right = i - 1;
int key = a[i];
while (left <= right) {
int mid = (left + right) / 2;
if (type * a[mid] > type * key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (int j = i - 1; j >= left; j--) {
a[j + 1] = a[j];
}
a[left] = key;
}
}
```
这样,你就可以用 BiInsertion 函数将输入的乱序数组按升序排列了。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)