数据结构之查找算法总结

public int (int[] arr, int target){
    int n = arr.length;
    int res = -1;
    for(int i = 0; i < n; i++){
        if(arr[i] == target){
            res = i;
            break;
        }
    }
    
    return res;
}

public int search(int[] nums, int target) {
        int lo = 0,hi = nums.length - 1;
        int res = -1;

        while(lo <= hi){
            int mid = lo + (hi - lo) /2;
            if( nums[mid] < target){
                lo = mid + 1;
            }
            else if( target < nums[mid]){
                hi = mid - 1;
            }
            else{
                res = mid;
                break;
            }
        }

        return res;
        
    }

public class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){ val = x;}
}

class BST{
    
    // serach in BST
    public TreeNode searchBST(TreeNode root, int val) {
        if( root == null ) return root;
        
        while( root != null){
            if( root.val == val ) return root;
            
            if( root.val > val ){
                root = root.left;
            }
            else{
                root = root.right;
            }
        }
        
        return root;
    }
    
   //validation
   public boolean isValidBST(TreeNode root) {
        if(root == null ) return true;
        
        List<Integer> res  = new ArrayList<>();
        
        inorder(root, res);
        
        for(int i = 0; i < res.size() - 1; i++){
            if( res.get(i+ 1) <= res.get(i) )
                return false;
        }
        
        return true;
    }
    
    private void inorder(TreeNode root, List<Integer> res){
        if( root == null) return ;
        
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
    
    //insert
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null)    return new TreeNode(val);
        if(val < root.val) root.left = insertIntoBST(root.left, val);
        else if (val > root.val)            root.right = insertIntoBST(root.right, val);
        else	x.val = val;
        return root;
    }
}

//delete 
 public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null ) return null;
        
        if(key < root.val) root.left = deleteNode(root.left, key);
        else if( key > root.val) root.right = deleteNode(root.right, key);
        else{
            if(root.right == null) return root.left;
            if(root.left == null) return root.right;
            TreeNode t = root;
            root = min(t.right);
            root.right = deleteMin(t.right);
            root.left = t.left;
        }
        
        return root;
            
    }
    
    private TreeNode min(TreeNode root){
        if(root.left == null) return root;
        else return min(root.left);
    }
    
    private TreeNode deleteMin(TreeNode x){
        if(x.left == null ) return x.right;
        x.left = deleteMin(x.left);
        return x;
    }