用JAVA描写在给定长度为n的升序序列A[1...n]中,用二分搜索搜索元素X
时间: 2023-05-28 08:06:17 浏览: 46
public class BinarySearch {
public static int binarySearch(int[] A, int x) {
int left = 0;
int right = A.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid] == x) {
return mid;
} else if (A[mid] > x) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
// 测试代码
public class Test {
public static void main(String[] args) {
int[] A = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int x = 5;
int index = BinarySearch.binarySearch(A, x);
System.out.println(index);
}
}
相关问题
用JAVA描写在给定长度为n的升序序列A[1...n]中,搜索元素X
的过程,如果找到就返回位置,否则返回-1。
代码如下:
```java
public static int binarySearch(int[] A, int X) {
int left = 0, right = A.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid] == X) {
return mid;
} else if (A[mid] < X) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
解释:
1. 定义左右指针left和right,初始值分别为0和n-1,表示搜索区间为整个序列A。
2. 进入循环,只要左指针小于等于右指针,就一直搜索。
3. 计算中间位置mid,如果中间元素等于X,则直接返回mid。
4. 如果中间元素小于X,则说明X在右半部分,将左指针移动到mid+1。
5. 如果中间元素大于X,则说明X在左半部分,将右指针移动到mid-1。
6. 如果循环结束仍未找到X,则返回-1。
时间复杂度:O(logn)。
用JAVA实现二分搜索,给定已按升序排列好序的n个元素a[0]
到a[n-1]和一个目标值target,返回目标值在数组中的索引,如果目标值不存在,则返回-1。
可以使用以下代码实现二分搜索:
public static int binarySearch(int[] arr, int target) {
int left = ;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
其中,left和right分别表示搜索范围的左右边界,mid表示中间位置的索引。在每一次循环中,比较中间位置的值和目标值的大小关系,如果相等,则返回中间位置的索引;如果目标值比中间位置的值大,则在右半部分继续搜索;否则在左半部分继续搜索。如果搜索完整个数组仍然没有找到目标值,则返回-1。