博客

二分查找（递归）

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int binary_sort(vector<int> sort_vec,int begin,int end,int goal_digit)
{
    if (begin > end){
        return false;
    }
   
    int mid = (end+begin)/2;
    
    if (goal_digit == sort_vec[mid]){
        return true;
    }
    
    if (goal_digit > sort_vec[mid]){
        return (binary_sort(sort_vec,mid+1,end,goal_digit));
    }else{
        return (binary_sort(sort_vec,0,mid-1,goal_digit));
    }
    
    return true;
}

int main()
{
    int result;
    int sort_arr[] = {-1,1,4,5,6,7,88,100};
    int rand_arr[] = {1,88,44,2,100};
    vector<int> sort_vec;
    vector<int> rand_vec;
    vector<int> res;

    /*创建一个向量存放排序数*/
    for (int i=0; i<8; i++){
        sort_vec.push_back(sort_arr[i]);
    }

    /*创建一个向量存放随机数*/
    for (int i=0; i<5; i++){
        rand_vec.push_back(rand_arr[i]);
    }

    for (int i=0; i<rand_vec.size(); i++){
        result = binary_sort(sort_vec,0,sort_vec.size()-1,rand_vec[i]);
        res.push_back(result);
    }

    for (int i=0; i<res.size(); i++){
        cout << res[i] << " "; 
    }
    cout << "\n";

    return 0;
}

二分查找（循环）

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool binary_sort(vector<int> sort_vec,int begin,int end,int goal_digit)
{
    while (begin <= end){
        int mid = (begin+end)/2;
        if (goal_digit == sort_vec[mid]){
            return true;
        }else if (goal_digit < sort_vec[mid]){
            end = mid - 1;
        }else if (goal_digit > sort_vec[mid]){
            begin = mid + 1;
        }
    }

    return false;
}

int main()
{
    int result;
    int sort_arr[] = {-1,1,4,5,6,7,88,100};
    int rand_arr[] = {1,88,44,2,100};
    vector<int> sort_vec;
    vector<int> rand_vec;
    vector<int> res;

    /*创建一个向量存放排序数*/
    for (int i=0; i<8; i++){
        sort_vec.push_back(sort_arr[i]);
    }

    /*创建一个向量存放随机数*/
    for (int i=0; i<5; i++){
        rand_vec.push_back(rand_arr[i]);
    }

    for (int i=0; i<rand_vec.size(); i++){
        result = binary_sort(sort_vec,0,sort_vec.size()-1,rand_vec[i]);
        res.push_back(result);
    }

    for (int i=0; i<res.size(); i++){
        cout << res[i] << " "; 
    }
    cout << "\n";

    return 0;
}

插入位置

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int SearchInsert(vector<int> &sort_vec,int goal)
{
    int begin = 0;
    int end = sort_vec.size() - 1;

    while (1){
        int mid = (end+begin)/2;

        if (goal == sort_vec[mid]){
            return mid;
        }else if (goal < sort_vec[mid]){
            if (mid == 0 || goal > sort_vec[mid-1]){
                return mid;
            }
            end = mid - 1;
        }else if (goal > sort_vec[mid]){
            if (mid == sort_vec.size()-1 || goal < sort_vec[mid+1]){
                return mid+1;
            }
            begin = mid+1;
        }
    }
    
    return 0;;
}

int main()
{
    int tmp;
    int sort_arr[] = {1,3,5,6};
    vector<int> result;
    vector<int> sort_vec;
    vector<int> rand_vec;

    /*创建一个向量存放排序数*/
    for (int i=0; i<4; i++){
        sort_vec.push_back(sort_arr[i]);
    }

    /*创建一个向量存放随机数*/
    for (int i=0; i<8; i++){
        rand_vec.push_back(i);
    }

    for (int i=0; i<rand_vec.size(); i++){
        tmp = SearchInsert(sort_vec,rand_vec[i]);
        result.push_back(tmp);
    }

    for (int i=0; i<result.size(); i++){
        cout << i<<" "<<result[i] <<endl; 
    }

    return 0;
}

区间查找

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class soluction
{
public:
    int left_search(vector<int> sort_vec,int goal)
    {
        int mid = 0;
        int begin = 0;
        int end = sort_vec.size() - 1;
        
        while (begin <= end){
            mid = (begin+end)/2;
            if (sort_vec[mid] == goal){
                if (mid == 0 || goal > sort_vec[mid - 1]){
                    return mid;
                }
                end = mid -1;
            }else if (goal > sort_vec[mid]){
                    begin = mid+1;
            }else if (goal < sort_vec[mid]){
                    end = mid - 1;
            }
        }
        
        return -1;
    }
    
    int right_search(vector<int> &sort_vec,int goal)
    {
        int begin = 0;
        int mid = 0;
        int end = sort_vec.size() - 1;
        
        while (begin <= end){
            mid = (begin + end)/2;
            cout << mid << " " << sort_vec[mid+1]<< " " << sort_vec[mid]<<endl;
            if (goal == sort_vec[mid]){
                if (mid == sort_vec.size()-1 || goal < sort_vec[mid + 1]){
                    return mid;
                }
                begin = mid+1;
            }else if (goal > sort_vec[mid]){
                begin = mid + 1;
            }else if (goal < sort_vec[mid]){
                end = mid - 1;
            }
        }
        
        return -1;
    }
};

int main()
{
    class soluction solve;
    vector<int> sort_vec;
    int sort_arr[] = {5,7,7,8,8,8,8,10};
    
    for (int i=0; i<sizeof(sort_arr)/sizeof(int); i++){
        sort_vec.push_back(sort_arr[i]);
    }

    cout << "the left is "<<solve.left_search(sort_vec,10)
    <<"\nthe right is "<<solve.right_search(sort_vec,10)<<endl;

    return 0;
}

旋转数组查找

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class soluction
{
public:
    int find_locate(vector<int> rotate_arr,int goal)
    {
        int mid = 0;
        int begin = 0;
        int end = rotate_arr.size() - 1;
        
        while (begin <= end){
            mid = (begin+end)/2;
            if(goal == rotate_arr[mid]){
                return mid;
            }else if (goal < rotate_arr[mid]){
                if (rotate_arr[begin] < rotate_arr[mid]){
                    if (goal < rotate_arr[begin]){
                        begin = mid + 1;
                    }else{
                        end = mid - 1;
                    }
                }else if (rotate_arr[begin] > rotate_arr[mid]){
                    end = mid - 1;
                }else{
                    begin = mid + 1;
                }
            }else{
                if (rotate_arr[begin] < rotate_arr[mid]){
                    begin = mid + 1;
                }else if (rotate_arr[begin] > rotate_arr[mid]){
                    if (goal < rotate_arr[begin]){
                        begin = mid+1;
                    }else{
                        end = mid -1;
                    }
                }else{
                    begin = mid + 1;
                }
            }
        }
        return -1;
    }
};


int main()
{
    class soluction solve;
    vector<int> sort_vec;
    int sort_arr[] = {7,8,9,1,2,3,4,5,6};
    
    for (int i=0; i<sizeof(sort_arr)/sizeof(int); i++){
        sort_vec.push_back(sort_arr[i]);
    }
    
    for (int i=0; i<4; i++){
        cout << solve.find_locate(sort_vec,i)<<endl;
    }

    return 0;
}

二叉查找树编码与解码

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

struct Node{
    int val;
    Node *left;
    Node *right;
    Node(int x):val(x),left(NULL),right(NULL){};
};

class solution{
public:
    struct Node * BSF_insert(struct Node *root,int val)
    {
        struct Node *tmp = NULL;    
    
        if (!root){
            tmp=new struct Node(val);
            return tmp;
        }
        
        if (val >= root->val){
            if (!root->right){
                tmp=new struct Node(val);
                root->right = tmp;
                return root;
            }
            BSF_insert(root->right,val);
        }else{
            if (!root->left){
                tmp=new struct Node(val);
                root->left = tmp;
                return root;
            }
            BSF_insert(root->left,val);
        }

        return root;
    }
    
    void preorder_binary_t(struct Node *root,int times)
    {
        if (!root){
            return;
        }
        
        for (int i=0; i<times; i++){
            cout << "--" ;
        }
        
        times++;
        cout << root->val<<endl;
        preorder_binary_t(root->left,times);
        preorder_binary_t(root->right,times);
        
        return;
    }
    
    void encode_binary_t(struct Node *root,string &encode)
    {   
        int tmp_num = 0;
        string tmp_encode;
        if (!root){
            return;
        }
        
        tmp_num = root->val;
        while(tmp_num != 0){
            tmp_encode += (tmp_num%10 + '0');
            tmp_num=tmp_num/10;
        }
        for (int i=tmp_encode.length()-1; i>=0 ; i--){
            encode += tmp_encode[i];
        }
        encode += "#";
        encode_binary_t(root->left,encode);
        encode_binary_t(root->right,encode);
        
        return;
    }

    struct Node* encode_binary_t(string &encode)
    {
        int val = 0;
        int tmp = 0;
        struct Node *root = NULL;
        
        for (int i=0; i<encode.length(); i++){
            if (encode[i] == '#'){
                cout << val <<endl;
                root=BSF_insert(root,val);
                val = 0;
                i++;
            }
            val = val * 10 + encode[i] - '0';
        }
        
        return root;
    }        

    void delete_binary_t(struct Node *root)
    {
        if (!root){
            return;
        }
          
        delete_binary_t(root->left);
        delete_binary_t(root->right);
        delete root;
        
        return;
    }    
    
};

int main()
{
    class solution solve;
    string result;
    struct Node *root = NULL;
    struct Node *new_root;
    int arr[]={8,3,10,1,6,15};
  
    //字符串插入
    for (int i=0; i<sizeof(arr)/sizeof(int); i++){
        root=solve.BSF_insert(root,arr[i]);
    }

    //前序遍历
    solve.preorder_binary_t(root,0);
    
    //字符串编码
    solve.encode_binary_t(root,result);
    cout << result <<endl;
    
    //字符串解码
    new_root = solve.encode_binary_t(result);
    solve.preorder_binary_t(new_root,0);
    
    //清除二叉树
    solve.delete_binary_t(root);
    solve.delete_binary_t(new_root);
    
    return 0;
}

逆序树（二叉查找树）

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

struct Node{
    int val;
    int small_count;
    Node *left;
    Node *right;
    Node(int x):val(x),left(NULL),right(NULL),small_count(0){};
};

class solution{
public:
    struct Node *BSF_insert(struct Node *root,int val,int &small_count)
    {
        struct Node *tmp = NULL;
        
        if (!root){
            root = new struct Node(val);
            return root;
        }

        if (val <= root->val){
            root->small_count++;
            if (!root->left){
                tmp = new struct Node(val);
                root->left = tmp;
                return root;
            }
            
            BSF_insert(root->left,val,small_count);
        }else{
            small_count = small_count+root->small_count+1;
            if (!root->right){
                tmp = new struct Node(val);
                root->right = tmp;
                
                return root;
            }

            BSF_insert(root->right,val,small_count);
        }
        
        return root;
    }
   
    vector<int> get_inverse(vector<int> arr)
    {
        vector<int> result;
        struct Node *root = NULL;
        int small_count = 0;
        
        for (int i=arr.size() -1; i>=0; i--){
            root=BSF_insert(root,arr[i],small_count);
            result.push_back(small_count);
            small_count = 0;
        }
        BFS_search(root,0);
        return result;
    }
    
    void BFS_search(struct Node *root,int times)
    {
        if(!root){
            return;
        }
        for (int i=0; i<times; i++){
            cout <<"--";
        }
        times++;
        cout << root->val<<endl;
        BFS_search(root->left,times);
        BFS_search(root->right,times);
    }
};

int main()
{
    vector<int> result;
    class solution solve;
    int unorder_num[] = {5,-7,9,1,3,5,-2,1};
    vector<int> unorder_vec;
    
    for (int i=0; i<sizeof(unorder_num)/sizeof(int); i++){
        unorder_vec.push_back(unorder_num[i]);
    }
    
    result=solve.get_inverse(unorder_vec);
    
    for (int i=0; i<result.size(); i++){
        cout<<result[i]<<" ";
    }
    cout << "\n";
    return 0;
}