用java代码写出,请用二分法写出一个相应的查找函数,使其接受一个有序的数组和一个数字,返回该数字在数组中的位置,若找不到则返回-1。
时间: 2024-05-07 09:23:58 浏览: 91
好的,我可以为您编写二分查找函数的示例代码。以下是示例代码:
```java
public class BinarySearch {
public int findIndex(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
```
以上代码实现了一个名为`findIndex`的函数,该函数接受一个有序数组`nums`和一个目标数字`target`,并返回该数字在数组中的下标,如果找不到则返回-1。这个函数使用二分查找算法来实现,可以快速找到目标数字。
相关问题
帮我找一个用Java写的二分法排序代码
### 回答1:
这是一个使用 Java 语言实现二分法排序的示例代码:
```
import java.util.Arrays;
public class BinarySort {
public static void main(String[] args) {
// 排序前数组
int[] array = {3, 7, 1, 2, 9, 4, 5};
// 排序
sort(array);
// 打印排序后的数组
System.out.println(Arrays.toString(array));
}
public static void sort(int[] array) {
for (int i = 1; i < array.length; i++) {
int value = array[i];
int j = i - 1;
// 二分法查找插入位置
int left = 0;
int right = i - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] > value) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 将大于 value 的元素向后移动一位
while (j >= left) {
array[j + 1] = array[j];
j--;
}
// 将 value 插入到正确的位置
array[left] = value;
}
}
}
```
上面的代码实现了一种插入排序的算法,其中使用了二分法来查找每个元素应该插入的位置。这个算法的时间复杂度为 O(n log n),相对于普通的插入排序(时间复杂度为 O(n^2))而言,运行速度要快得多。
### 回答2:
以下是使用Java编写的二分法排序代码示例:
```java
import java.util.Arrays;
public class BinarySearchSort {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 1, 4};
binarySearchSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void binarySearchSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int left = 0;
int right = i - 1;
int index = binarySearch(arr, key, left, right);
for (int j = i - 1; j >= index; j--) {
arr[j + 1] = arr[j];
}
arr[index] = key;
}
}
public static int binarySearch(int[] arr, int key, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
```
该代码实现了二分法排序的功能。在main函数中创建一个整型数组arr,并将数组传入binarySearchSort方法中进行排序。binarySearchSort方法使用二分查找法找到待插入元素的位置index,然后通过将右侧的元素向右移动一个位置,并将key插入到index处,实现了排序。最后,打印出排序后的数组。
### 回答3:
下面是用Java写的一个二分法排序的示例代码:
```java
import java.util.Arrays;
public class BinarySearchSort {
public static void main(String[] args) {
int[] array = {10, 3, 8, 5, 2, 7, 6, 9, 1, 4};
System.out.println("排序前:" + Arrays.toString(array));
binarySearchSort(array);
System.out.println("排序后:" + Arrays.toString(array));
}
public static void binarySearchSort(int[] array) {
int len = array.length;
for (int i = 0; i < len; i++) {
int left = 0, right = i - 1;
int temp = array[i];
int insertIndex = -1;
// 使用二分法定位插入位置
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] < temp) {
left = mid + 1;
} else {
right = mid - 1;
}
}
insertIndex = left;
// 将插入位置及之后的元素后移
for (int j = i - 1; j >= insertIndex; j--) {
array[j + 1] = array[j];
}
array[insertIndex] = temp;
}
}
}
```
该示例中,我们使用二分法将数组中的元素逐个插入到有序区间中。首先,初始化有序区间为第一个元素,然后从第二个元素开始,使用二分法找到插入位置,再将插入位置后的元素依次后移。最后,在插入位置处插入该元素,完成一轮插入操作。最终,整个数组就会被排序。运行该代码,你将看到输出的排序结果。
希望以上内容对你有帮助!
阅读全文