查找演算法
二分查找
非遞回版的
// 二分查找法,在有序陣列arr中,查找target
// 如果找到target,回傳相應的索引index
// 如果沒有找到target,回傳-1
template<typename T>
int binarySearch(T arr[], int n, T target){
// 在arr[l...r]之中查找target
int l = 0, r = n-1;
while( l <= r ){
//int mid = (l + r)/2;
// 防止極端情況下的整形溢位，使用下面的邏輯求出mid
int mid = l + (r-l)/2;
if( arr[mid] == target )
return mid;
if( arr[mid] > target )
r = mid - 1;
else
l = mid + 1;
}
return -1;
}
遞回版的
// 用遞回的方式寫二分查找法
template<typename T>
int __binarySearch2(T arr[], int l, int r, T target){
if( l > r )
return -1;
//int mid = (l+r)/2;
// 防止極端情況下的整形溢位，使用下面的邏輯求出mid
int mid = l + (r-l)/2;
if( arr[mid] == target )
return mid;
else if( arr[mid] > target )
return __binarySearch2(arr, l, mid-1, target);
else
return __binarySearch2(arr, mid+1, r, target);
}
template<typename T>
int binarySearch2(T arr[], int n, T target){
return __binarySearch2( arr , 0 , n-1, target);
}
floor實作
二分查找法, 在有序陣列arr中, 查找target,如果找到target, 回傳第一個target相應的索引index,如果沒有找到target, 回傳比target小的最大值相應的索引, 如果這個最大值有多個, 回傳最大索引,如果這個target比整個陣列的最小元素值還要小, 則不存在這個target的floor值, 回傳-1
template<typename T>
int floor(T arr[], int n, T target){
assert( n >= 0 );
// 尋找比target小的最大索引
int l = -1, r = n-1;
while( l < r ){
// 使用向上取整避免死回圈
int mid = l + (r-l+1)/2;
if( arr[mid] >= target )
r = mid - 1;
else
l = mid;
}
assert( l == r );
// 如果該索引+1就是target本身, 該索引+1即為回傳值
if( l + 1 < n && arr[l+1] == target )
return l + 1;
// 否則, 該索引即為回傳值
return l;
}
ceil實作
二分查找法, 在有序陣列arr中, 查找target,如果找到target, 回傳最后一個target相應的索引index,如果沒有找到target, 回傳比target大的最小值相應的索引, 如果這個最小值有多個, 回傳最小的索引,如果這個target比整個陣列的最大元素值還要大, 則不存在這個target的ceil值, 回傳整個陣列元素個數n
template<typename T>
int ceil(T arr[], int n, T target){
assert( n >= 0 );
// 尋找比target大的最小索引值
int l = 0, r = n;
while( l < r ){
// 使用普通的向下取整即可避免死回圈
int mid = l + (r-l)/2;
if( arr[mid] <= target )
l = mid + 1;
else // arr[mid] > target
r = mid;
}
assert( l == r );
// 如果該索引-1就是target本身, 該索引+1即為回傳值
if( r - 1 >= 0 && arr[r-1] == target )
return r-1;
// 否則, 該索引即為回傳值
return r;
}
二分查找樹插入與查找與遍歷演算法
遞回寫法
#include <iostream>
using namespace std;
// 二分搜索樹
template <typename Key, typename Value>
class BST{
private:
// 樹中的節點為私有的結構體, 外界不需要了解二分搜索樹節點的具體實作
struct Node{
Key key;
Value value;
Node *left;
Node *right;
Node(Key key, Value value){
this->key = key;
this->value = https://www.cnblogs.com/ygjzs/p/value;
this->left = this->right = NULL;
}
};
Node *root; // 根節點
int count; // 樹中的節點個數
public:
// 建構式, 默認構造一棵空二分搜索樹
BST(){
root = NULL;
count = 0;
}
~BST(){
destroy( root );
}
// 回傳二分搜索樹的節點個數
int size(){
return count;
}
// 回傳二分搜索樹是否為空
bool isEmpty(){
return count == 0;
}
// 向二分搜索樹中插入一個新的(key, value)資料對
void insert(Key key, Value value){
root = insert(root, key, value);
}
// 查看二分搜索樹中是否存在鍵key
bool contain(Key key){
return contain(root, key);
}
// 在二分搜索樹中搜索鍵key所對應的值，如果這個值不存在, 則回傳NULL
Value* search(Key key){
return search( root , key );
}
// 二分搜索樹的前序遍歷
void preOrder(){
preOrder(root);
}
// 二分搜索樹的中序遍歷
void inOrder(){
inOrder(root);
}
// 二分搜索樹的后序遍歷
void postOrder(){
postOrder(root);
}
// 二分搜索樹的層序遍歷
void levelOrder() {
if (root == NULL) return;
queue q;
q.push(root);
while (!q.empty()) {
Node *node = q.front();
q.pop();
cout << node->key << endl;
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
}
// 從二分搜索樹中洗掉最小值所在節點
void removeMin(){
if( root )
root = removeMin( root );
}
// 從二分搜索樹中洗掉最大值所在節點
void removeMax(){
if( root )
root = removeMax( root );
}
// 從二分搜索樹中洗掉鍵值為key的節點
void remove(Key key){
root = remove(root, key);
}
private:
// 向以node為根的二分搜索樹中, 插入節點(key, value), 使用遞回演算法
// 回傳插入新節點后的二分搜索樹的根
Node* insert(Node *node, Key key, Value value){
if( node == NULL ){
count ++;
return new Node(key, value);
}
if( key == node->key )
node->value = value;
else if( key < node->key )
node->left = insert( node->left , key, value);
else // key > node->key
node->right = insert( node->right, key, value);
return node;
}
// 查看以node為根的二分搜索樹中是否包含鍵值為key的節點, 使用遞回演算法
bool contain(Node* node, Key key){
if( node == NULL )
return false;
if( key == node->key )
return true;
else if( key < node->key )
return contain( node->left , key );
else // key > node->key
return contain( node->right , key );
}
// 在以node為根的二分搜索樹中查找key所對應的value, 遞回演算法
// 若value不存在, 則回傳NULL
Value* search(Node* node, Key key){
if( node == NULL )
return NULL;
if( key == node->key )
return &(node->value);
else if( key < node->key )
return search( node->left , key );
else // key > node->key
return search( node->right, key );
}
// 對以node為根的二叉搜索樹進行前序遍歷, 遞回演算法
void preOrder(Node* node){
if( node != NULL ){
cout<key<left);
preOrder(node->right);
}
}
// 對以node為根的二叉搜索樹進行中序遍歷, 遞回演算法
void inOrder(Node* node){
if( node != NULL ){
inOrder(node->left);
cout<key<right);
}
}
// 對以node為根的二叉搜索樹進行后序遍歷, 遞回演算法
void postOrder(Node* node){
if( node != NULL ){
postOrder(node->left);
postOrder(node->right);
cout<key<left );
destroy( node->right );
delete node;
count --;
}
}
// 洗掉掉以node為根的二分搜索樹中的最小節點
// 回傳洗掉節點后新的二分搜索樹的根
Node* removeMin(Node* node){
if( node->left == NULL ){
Node* rightNode = node->right;
delete node;
count --;
return rightNode;
}
node->left = removeMin(node->left);
return node;
}
// 洗掉掉以node為根的二分搜索樹中的最大節點
// 回傳洗掉節點后新的二分搜索樹的根
Node* removeMax(Node* node){
if( node->right == NULL ){
Node* leftNode = node->left;
delete node;
count --;
return leftNode;
}
node->right = removeMax(node->right);
return node;
}
// 洗掉掉以node為根的二分搜索樹中鍵值為key的節點, 遞回演算法
// 回傳洗掉節點后新的二分搜索樹的根
Node* remove(Node* node, Key key){
if( node == NULL )
return NULL;
if( key < node->key ){
node->left = remove( node->left , key );
return node;
}
else if( key > node->key ){
node->right = remove( node->right, key );
return node;
}
else{ // key == node->key
// 待洗掉節點左子樹為空的情況
if( node->left == NULL ){
Node *rightNode = node->right;
delete node;
count --;
return rightNode;
}
// 待洗掉節點右子樹為空的情況
if( node->right == NULL ){
Node *leftNode = node->left;
delete node;
count--;
return leftNode;
}
// 待洗掉節點左右子樹均不為空的情況
// 找到比待洗掉節點大的最小節點, 即待洗掉節點右子樹的最小節點
// 用這個節點頂替待洗掉節點的位置
Node *successor = new Node(minimum(node->right));
count ++;
successor->right = removeMin(node->right);
successor->left = node->left;
delete node;
count --;
return successor;
}
}
};
int main() {
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57194.html
標籤：其他
上一篇：對圖片中值模糊運算出錯的問題
下一篇：MATLAB中如何檢測輸入影像中任意三角形的三邊長，面積和重心？要利用標尺（標尺是自己手機拍的）求大佬指教啊啊啊啊