Search for a range

题目描述

Given a sorted array of integers, find the starting and ending position of a given target value.Your algorithm's runtime complexity must be in the order of O(log n).If the target is not found in the array, return[-1, -1].For example,
Given[5, 7, 7, 8, 8, 10]and target value 8,
return[3, 4].

题目解析

关键词:有序数组复杂度O(logn)。这就很明显说明了一件事,题目想让我们使用二分查找的方法来实现。在C++的STL里面,已经由现成的函数帮我们实现返回第一个位置和最后一个位置的函数,也就是low_bound()和upper_bound()。

low_bound()和upper_bound()都是使用二分查找实现查找工作,两者都是返回一个迭代器(iterator),但是不同的是,low_bound()返回的是第一个大于或等于num的数字,找到返回该数字的地址,(若数组中没有该元素,则返回end),upper_bound()返回第一个大于num的数字的位置(如果数组没有该元素,同理)。因此,如果我们对low_bound()返回的地址减去起始地址,就得到了第一次出现目标数字的位置,对upper_bound()减去起始地址,就得到了目标数字下一个位置,再减1,得到最后一次出现目标数字的位置。代码实现见代码实现1。

这是一种取巧的方法,使用了STL中的Algorithm。但是,这样除了展示你会使用STL中的algorithm之外没有任何用处,所以还是需要去实现这个寻找过程。这个过程就是实现二分查找。

其实现具体过程很基础,不再重述。

代码实现1

代码实现2

Validate Binary Search Tree

题目描述

Given a binary tree, determine if it is a valid binary search tree (BST).Assume a BST is defined as follows:The left subtree of a node contains only nodes with keys less than the node's key.The right subtree of a node contains only nodes with keys greater than the node's key.Both the left and right subtrees must also be binary search trees.

题目解析

暂无

代码实现