二分查找java
时间: 2023-07-18 18:14:26 浏览: 53
二分查找(Binary Search)是一种在有序数组中查找某一特定元素的搜索算法。其基本思想是:每次取数组中间的元素与目标值进行比较,如果中间元素等于目标值,则查找成功;如果中间元素大于目标值,则在数组左半部分继续查找;如果中间元素小于目标值,则在数组右半部分继续查找。重复以上步骤,直到找到目标值或确定没有目标值为止。
以下是二分查找的Java实现:
```
public static int binarySearch(int[] arr, int target) {
int left = 0;
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; // 表示未找到目标元素
}
```
在上述代码中,我们定义了一个 `binarySearch` 方法,该方法接收两个参数,一个是有序数组 `arr`,另一个是目标值 `target`。首先,我们定义两个指针 `left` 和 `right`,分别指向数组的左端和右端。然后,我们进入循环,每次计算中间元素的下标 `mid`,并判断中间元素与目标值的大小关系。如果中间元素等于目标值,则查找成功,返回其下标;如果中间元素小于目标值,则在数组右半部分继续查找,将 `left` 指针指向 `mid + 1`;如果中间元素大于目标值,则在数组左半部分继续查找,将 `right` 指针指向 `mid - 1`。最后,如果循环结束仍未找到目标元素,则返回 `-1`。