二分查找Java
时间: 2023-07-18 14:03:24 浏览: 79
二分查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。它的思想是,将数组分成两个部分,判断要查找的元素与中间元素的大小关系,如果相等则返回中间元素的下标,如果要查找的元素比中间元素小,则在左半部分继续查找,否则在右半部分继续查找,直到找到要查找的元素或者数组中没有剩余元素为止。
以下是一个简单的Java实现:
```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; // 如果没找到,返回-1
}
```
在该实现中,我们使用了两个指针left和right来表示当前搜索的范围。在每一次循环中,我们计算中间元素的下标mid,然后与目标元素进行比较。如果相等,则返回mid;如果目标元素比中间元素小,则在左半部分继续查找,即将right指针移动到mid-1;如果目标元素比中间元素大,则在右半部分继续查找,即将left指针移动到mid+1。如果最终没有找到目标元素,则返回-1。
阅读全文