二分查找

二分搜索英语binary search是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始如果中间元素正好是要查找的元素则搜索过程结束如果某一特定元素大于或者小于中间元素则在数组大于或小于中间元素的那一半中查找而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。时间复杂法为O(log)的目前所学算法中为二分法莫属而且在一系列的其他算法诸如排序等因为二分的思想而常使得其时间复杂度降为O(nlogn)而一般情况下是O(n*n)。然而二分法虽然高效但很具有局限性用于二分查找的序列必须具有如下特征1存储在数组中在链表中就不能实现二分查找了。2序列有序。二分查找的缺陷二分查找的效率令人向往但固有的缺陷亦也使人恼火首先它要求是数组其次还要求有序在对元素进行删除增加操作时很耗时时间复杂度为O(n)而一种好的办法是使用二叉查找树它能在O(nlogn)内构建树也能在O(logn)内查找目标。Leetcode中的二分题目https://blog.csdn.net/u013007900/article/details/53363571