leetcode总结无止境系列之查找

在查找出最基础、考查频率也挺高的便是二分查找</strong>。二分查找最常见的应用是在有序数组中查找元素。除了二分查找外,还有平衡二叉树、红黑树,但是这些一般不会作为点现场写代码考查,一般只需要熟练使用STL中的一些容器,常用的主要是set, map, deque, list, vector, stack。</p></p>

二分查找</span>
</p>

博客之前有两篇看编程珠玑时提到二分查找的文章,比较基础:编程珠玑2_啊哈!算法</a> 关于二分搜索</a>
应用:</strong>顺序数组中的元素查找,但是一般不会考这么简单,会考一些变形:(1)在一个有序数组中,找到某个特定元素出现的次数(2)旋转数组中元素的查找(3)求两个有序数组的中位数

二分查找代码:</strong>
[code text="lang"]
int BinarySearch(int *arr, int n, int target)
{
if(arr == NULL || n <= 0)
return -1;
int i = 0, j = n - 1;
while(i <= j)
{
int mid = (i + j) / 2;
if(arr[mid] == target)
return mid;
else if(arr[mid] > target)
j = mid - 1;
else
i = mid + 1;
}
}
[/code]
</p></p>

平衡树</span>
</p>

红黑树是一种特殊的平衡二叉树,STL里的set和map(还有multiset和multimap)都是用红黑树作为底层实现的。平衡树中用O(logn)的时间查找某个数或者查找不超过阈值的某个最大(最小)值,这些操作都跟上面的几种二分查找一一对应。但是平衡树的优势在于它是可以动态插入删除数据的(这个你用数组就不行了),缺点在于面试时你是没办法自己写一个平衡树的。一个应用例子是:从数组中找和最接近给定值target的连续子数组(数组有负)。可以这样做:求出sum数组,对于sum[i],从[i+1,n-1]中查找一个最接近sum[i]+target的值,查找方法是,sum存到一个multiset里面(平衡树),每次i+1之后,把sum[i+1]从multiset中清除。时空复杂度O(nlogn)+O(n)。
关于红黑树(或者其他平衡树)的介绍可以看看这个文章:教你透彻了解红黑树</a></p></p>

leetcode上对应的题目:</span></p>
1、Search for a Range</a></p>

2、Median of Two Sorted Arrays

3、Search in Rotated Sorted Array</a></p>

4、Sqrt(x)</a></p>

5、Search in Rotated Sorted Array II</a></p>

6、Search Insert Position</a></p>

crystal /
Published under (CC) BY-NC-SA in categories 面试  tagged with 算法  leetcode