查找算法

本文主要是介绍查找算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

二分查找法,最省内存的查找算法

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

注意点

1.(low+high)/2 这种写法是有问题的如果是low和high特别大有可能精度丢失，可以使用low+(high-low)/2或者low+((high-low)>>1)
2.mid的取值问题，low=mid+1，high=mid-1。注意这里的 +1 和 -1，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。比如，当 high=3，low=3 时，如果 a[3] 不等于 value，就会导致一直循环不退出

二分法的局限

1.必须查找数组里面的数据，不能是链表，因为二分法需要按照下标随机访问数据，数组通过下标访问数据的时间复杂度为O(1),链表是O(n),所以如果使用链表的话，二分查找复杂度就变得很高
2.必须是有序数组所以，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用
3.数据量太小的情况不适合二分查找，有个例外就是如果数据之间的比较特别耗时的情况下不管数据量的大小都而可以用二分查找法。

example

如何从100万整数中查找指定的数，内存限制100M，每个数据占8字节，这种情况下内存特别有限，我们可以在1000万整数在内存中先排序后使用二分查找，当然这中情况适合于多次查找的情况，只查找一次的话一次遍历就找到了。

课堂作业：
如何编程实现“求一个数的平方根”？要求精确到小数点后 6 位。

这篇关于查找算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！