JAVA实现二分查找
希赛网 2024-02-09 11:16:53
二分查找，也被称为折半查找，是一种在有序数组中查找指定元素的算法。在数据量较大的时候，二分查找比顺序查找的效率更高。下面，我将从算法原理、时间复杂度和JAVA代码实现三个方面，详细介绍二分查找算法。
一、算法原理
二分查找算法是将数组按照顺序排列，然后将查找的元素和数组的中间元素进行比较，如果相等则返回找到的元素的下标位置；如果查找的元素小于中间元素，则在数组的左半边继续进行二分查找；如果查找的元素大于中间元素，则在数组的右半边继续进行二分查找，直到找到或者查找结束。
二、时间复杂度
在最坏的情况下，二分查找算法的时间复杂度为O(logn)，其中n为数组的长度。在查找过程中，每次判断都会将查找范围缩小一半，那么最坏情况下的查找次数为log(n)，所以时间复杂度就是O(logn)。
三、JAVA代码实现
接下来，我们通过JAVA语言来实现二分查找算法。下面是JAVA代码实现：
```
public int binarySearch(int[] arr, int key) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > key) {
high = mid - 1;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
return mid;
}
}
return -1;
}
```
