public class bSearch{ public static int bSearch(int[]a; int x,int low,int high){ int mid; if(low>high) return -1; //查找不成功 mid=(low+high)/2; if(x == a[mid]) return mid; //查找成功 else if(x<a[mid]) return bSearch(a,x,low,mid-1); //在上半区查找 else return bSearch(a,x,mid+1,high);//在下半区查找 } public static void main(String[]args){ int [] a={1,3,4,5,17,18,31,33}; int x=17; int bn; bn = bSearch(a,x,0,7); if(bn==-1) System.out.println("x不在数组a中"); else System.out.println("x在数组a中,下标为:"+bn); } }
时间: 2023-05-28 21:02:07 浏览: 79
该代码实现了一个二分查找算法,可以查找给定数组a中是否存在指定元素x,并返回其索引值。
具体实现思路是将数组a分成两半,将中间位置mid作为比较对象,如果x与a[mid]相等,则查找成功,返回mid的值;如果x小于a[mid],则在数组的上半区查找,递归调用bSearch(a, x, low, mid-1);如果x大于a[mid],则在数组的下半区查找,递归调用bSearch(a, x, mid+1, high)。
该算法时间复杂度为O(log n),具有较好的效率。
相关问题
已有一个10个元素的整形数组a,且按值从小到大有序。输入一个整数x,然后在数组中查找x,如果找到,输出相应的下标,否则,输出"Not Found"。。 要求编写函数int Bsearch(int *p, int n, int x),找到返回下标,找不到返回-1。 函数接口定义: int Bsearch(int *p, int n, int x); 其中 p是数组首地址,n是数组元素个数,x是要查找的值。找到返回下标,找不到返回-1。
可以使用二分查找算法实现这个功能,以下是函数的代码实现:
```c
int Bsearch(int *p, int n, int x) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (p[mid] == x) {
return mid; // 找到返回下标
} else if (p[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 找不到返回-1
}
```
这个函数的实现中,使用 left 和 right 表示查找范围的左右边界,mid 表示中间位置。每次将要查找的区间缩小一半,直到找到或者无法找到为止。
具体来说,每次将中间位置的值与要查找的值比较,如果相等就返回中间位置的下标,如果中间位置的值小于要查找的值,就在右半部分继续查找,否则就在左半部分继续查找。
如果整个过程中没有找到要查找的值,就返回 -1 表示未找到。
使用示例:
```c
#include <stdio.h>
int Bsearch(int *p, int n, int x);
int main() {
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int x = 7;
int index = Bsearch(a, 10, x);
if (index >= 0) {
printf("找到了,下标是 %d\n", index);
} else {
printf("Not Found\n");
}
return 0;
}
int Bsearch(int *p, int n, int x) {
// ...
}
```
输出结果:
```
找到了,下标是 6
```
已有一个10个元素的整形数组a,且按值从小到大有序。输入一个整数x,然后在数组中查找x,如果找到,输出相应的下标,否则,输出"Not Found"。。 要求编写函数int Bsearch(int *p, int n, int x),找到返回下标,找不到返回-1。
```c
int Bsearch(int *p, int n, int x){
int left = 0, right = n - 1;
while(left <= right){
int mid = (left + right) / 2;
if(p[mid] == x){
return mid;
}else if(p[mid] < x){
left = mid + 1;
}else{
right = mid - 1;
}
}
return -1;
}
```