avatar

二分查找算法

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

二分查找也就是说,将待查找的数组取中间的索引值,拿这个中间的值和要查找的元素循环进行比对,如果相等则直接返回当前的索引;如果大于要查找的元素,则说明我们要查找的元素在中间元素的左侧;如果小于要查找的元素,则说明我们要查找的元素在中间元素的右侧;依次循环进行比对,就能够查到要查找的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int binarySearch(int [] arr, int searchNumber) {
// 先进行排序
Arrays.sort(arr);
// 左侧索引,默认为 0
int leftIndex = 0;
// 右侧索引,默认为数组的长度 - 1
int rightIndex = arr.length - 1;
while (leftIndex <= rightIndex) {
// 取数组元素的中间索引
int index = leftIndex + (rightIndex - leftIndex) / 2;
if (arr[index] == searchNumber) {
return index;
} else if (arr[index] > searchNumber) {
rightIndex = index - 1;
} else if (arr[index] < searchNumber) {
leftIndex = index + 1;
}
}
return -1;
}
文章作者: 惆怅客
文章链接: https://www.songhailong.com/articles/3102624d/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 惆怅客

评论