算法-二分查找法

• 二分查找法也叫折半查找法，每次折半进行查找，具有一定的局限性，依赖于顺序表结构以及数组，也就是说数据要是有序的，且每次都要通过下表来随机访问数据。时间复杂度为O(log2^n)
• 代码

public int bsearch(int[] a, int n, int value) {
 int low = 0;
 int high = n - 1;
 while (low <= high) {
 	int mid = (low + high) / 2;
 	if (a[mid] == value) {
 		return mid;
	} else if (a[mid] < value) {
 		low = mid + 1;
	 } else {
		 high = mid - 1;
	 }
 }
 return -1;
}

• 适用场景

1. 静态数据，没有频繁的删除、添加操作
2. 数据量太大也不适合二分查找，因为数组要求的是连续的内存空间

• 如何在1000万个整数中快速查找某个整数？
  先排序，再使用二分法查找即可。

• 如果数据使用链表来存储，进行二分查找法会有什么影响？
  链表查找时间复杂都会很高