Java基础算法-查找-二分查找

时间复杂度

怎么说呢。二分查找优缺点都是很明显的：
优点：就是查找的平均性能高，事件复杂度只有O（log（n））。但是缺点他也是
非常明显的，被查找的数组必须是有序的。
所以他最好是用于不经常变动但是查找频繁的数组

实现原理

在我的理解中：

1.拿要找的数与数组的中间数做比较，如果数组中的数大于就取0，到中值为新数组，否则则是（mid，last）作为新数组
2.拿新数组重复1步骤
3.重复1，2步骤直到找到那个值

代码实现

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
public static int binarySearch(int[] x, int n){
	int start = 0;
	int mid = -1;
	int end = x.length - 1;
	while(start <= end){
		mid = (start + end)/2;
		if(x[mid] == n){
			return mid;
		}else if(x[mid] > n){
			end = mid - 1;
		}else if(x[mid] < n){
			start = mid + 1;
		}
	}
}
public static void main(String[] args) {
			
	int[] nums = {1,2,3,4,5,6,8,11,45,89,102,99,47,66};
	Arrays.sort(nums);
		
	//
	int index = binarySearch(nums,47);
	System.out.println(index);
}

这样就是一个简单的实现了。

积累是一种习惯！

Algorithms