用JAVA实现二分搜索,给定已按升序排列好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x
时间: 2023-08-31 10:37:56 浏览: 43
### 回答1:
可以使用以下代码实现二分搜索:
public static int binarySearch(int[] arr, int x) {
int left = ;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
其中,arr为已按升序排列好序的n个元素,x为要查找的特定元素。函数返回值为x在数组中的下标,如果不存在则返回-1。
### 回答2:
二分搜索使用了分治的思想来快速找到特定元素x。具体实现如下:
1. 初始化搜索范围为整个数组a,即left = 0,right = n-1。
2. 进入循环,直到left > right:
- 计算中间位置mid = (left + right) / 2。
- 如果a[mid] == x,表示找到了特定元素x,返回mid。
- 如果a[mid] < x,表示x可能在a[mid+1:right]范围内,更新搜索范围,令left = mid + 1。
- 如果a[mid] > x,表示x可能在a[left:mid-1]范围内,更新搜索范围,令right = mid - 1。
3. 循环结束,表示未找到特定元素x,返回-1。
这个算法时间复杂度为O(log n),因为每次迭代都将搜索范围缩小一半。
以下是用JAVA编写的二分搜索代码示例:
```java
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) / 2;
if (a[mid] == x) {
return mid;
} else if (a[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int x = 6;
int result = binarySearch(a, x);
if (result == -1) {
System.out.println("Element not found.");
} else {
System.out.println("Element found at index " + result + ".");
}
}
}
```
以上代码示例将在数组a中搜索特定元素x,如果找到则打印其索引,如果未找到则打印“Element not found.”。