Java二分查找

理解:

在查找算法中,二分查找是一种效率较高并且实现起来较为简单的查找方法,不断的用中间索引去和被查找的值进行比较

注意:二分搜索有个前提,被查找的数组中的元素必须是有序排列的

思路

首先定义三个元素

最小索引 minIndex

最大索引maxIndex

中间索引 (minIndex + maxIndex) / 2

如果被查找的值大于中间索引 那么证明值在中间索引的右边 就从右边继续查找,此时最小索引便为中间索引+1 一直重复查找

如果被查找的值小于中间索引 那么证明值在中间索引的左边 就从左边继续查找,此时最大索引便为中间索引-1 一直重复查找

如果被查找的值刚好等于中间索引 那么就找到了

每次循环中间索引的值都需要重新定义

Dmeo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class BinarySearch {
/*
二分查找Demo
*/
public static void main(String [] args){
int [] num = {1,2,3,4,5,6,7,8,9};
int x = 6;
int a = binarySearch(num,x);
System.out.println("数字"+x+"出现在数组的第"+a+"个位置");
}

//二分查找方法
static int binarySearch(int [] num,int x){
int maxIndex = num.length-1;//最大索引(下标)为数组长度-1
int minIndex = 0;//最小索引(下标)为0
int middleIndex = (maxIndex + minIndex) / 2;//中间索引(下标)为最大索引加最小索引/2
while (minIndex<=maxIndex){//判断 如果最小索引小于等于最大索引 就执行循环
if (num[middleIndex] == x){//如果中间索引的值和判断的值相等
return middleIndex;//返回中间索引位置(也就是查找到的位置)
}else if (num[middleIndex]>x){//如果中间索引的值比判断的值要大则说明需要查找的值一定在左边
maxIndex = middleIndex-1;//像左边查找,所以最大索引就应该是中间索引-1
}else {
minIndex = middleIndex+1;//反之,证明值存在在中间索引右边 所以最小索引就该是中间索引加1
}
middleIndex = (maxIndex + minIndex) / 2;//每次查找结束后中间索引都会更新,因为最小索引和最大索引改变了
}
return 0;//如果上述情况都不符合 则返回0
}

}

二分查找和冒泡排序都属于java面试很常见的算法题

❤赏点钱让我买杯快乐水8❤