文档章节

查找算法总结

阿阿阿阿阿局
 阿阿阿阿阿局
发布于 2016/07/28 15:55
字数 993
阅读 26
收藏 1

查找算法:顺序查找、二分查找、分块查找、二叉查找树、B树、B+树

一、二分查找(常规)

题目描述:

(牛客网http://www.nowcoder.com/practice/28d5a9b7fc0b4a078c9a6d59830fb9b9?rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking)

对于一个有序数组,我们通常采用二分查找的方式来定位某一元素,请编写二分查找的算法,在数组中查找指定元素。

给定一个整数数组A及它的大小n,同时给定要查找的元素val,请返回它在数组中的位置(从0开始),若不存在该元素,返回-1。若该元素出现多次,请返回第一次出现的位置

测试样例:

[1,3,5,7,9],5,3
返回:1
public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        // write code here
        //递归实现
        //return binarySearch(A, val, n, 0);
        //非递归实现
        return binarySearch2(A, val, n);
    }
    
    //递归实现
    public int binarySearch(int[] pA, int pval, int high, int low){
        int mid = (high+low)/2;//相加
        if(low>high){
            return -1;
        }
        if(pA[mid]==pval){
            while(mid>0 && pA[mid-1]==pval){
                mid--;
            }
            return mid;
        }else if(pA[mid]>pval){//中间值大于pval
            return binarySearch(pA, pval, mid-1, low);
        }else{//中间值小于pval
            return binarySearch(pA, pval, high, mid+1);
        }
    }
    
    //非递归实现
    public int binarySearch2(int[] pA, int pval, int n){
        int high=n, low=0, mid;
        while(low<=high){
            mid = (high+low)/2;
            if(pA[mid]==pval){
                while(mid>0 && pA[mid-1]==pval){
                    mid--;
                }
                return mid;
            }else if(pA[mid]>pval){
                high = mid-1;
            }else{
                low = mid+1;
            }
        }
        return -1;
    }
}

二、二分查找变形题

1、查找旋转数组中最小值

题目描述:

(牛客网http://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking)

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

public class Solution {
    public int minNumberInRotateArray(int [] array) {
    	if(array.length==0){
            return 0;
        }else{
            return binarySearch(array);
        }
    }
    
    
    //两种情况: 
    //情况1:严格递增  第一个值总是大于最后一个值
    //寻找中间值,若中间值大于第一个值,则最小值位于中间值右侧
    //反之若中间值小于第一个值,则最小值位于中间值及中间值左侧
    //情况2:非递减(顺序查找,只需要查找后一个比前一个小即为最小值,若没有查到则返回第一个数据)
    public int binarySearch(int[] parray){
        int n=parray.length;
        int left=0, right=n-1, mid;
        while(left<=right){
            mid = (right+left)/2;
            //情况2
            if(parray[mid]==parray[left] && parray[mid]==parray[right]){
                boolean flag=false;
                for(int i=1; i<n; i++){
                    if(parray[i]<parray[i-1]){
                        flag = true;
                        return parray[i];
                    }
                }
                if(flag==false){
                   return parray[0]; 
                }
            }
            //情况1
            if(parray[mid]>parray[left]){//中间值大于第一个值
                left = mid+1;
            }else{//中间值小于第一个值
                right = mid;//最小值可能刚好是中间值
            }
            
        }
        return parray[right];
    }
}

有兴趣的可以看看详细分析:

参考网址:http://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba

 

 

三、二叉查找树

1、题目描述(很经典)

(牛客网http://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176)

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0){//数组为空的时候
            return false;
        }else{
            return PostOrderTraversal(sequence, 0, sequence.length-1);
        }
    }
    
    public boolean PostOrderTraversal(int[] data, int low, int high)  
	{  
         if(low >= high)  
	     {    
	          return true;  
	     }  
	     int split = -1;  
	     int i;  
	     boolean found = false;  
	     //to see if the data can be splited as ABC where c is the last one, all members in A < c, B > c  
	     for( i = low; i < high; i++)  
	     {  
	          if(data[i] > data[high] )  
	          {  
	               if(split == -1)  
	               {  
	                   split = i;  
	                   found = true;  
	               }  
	          }  
	          if(data[i] < data[high] && split != -1)  
	          {  
	              return false;  
	          }  
	     }  
	     if(! found )//only A < c or B > c;   
	     {  
	         return PostOrderTraversal(data, low, high-1);  
	     }  
	     else //recursive way   
	     {  
	         return PostOrderTraversal(data, low, split - 1) && PostOrderTraversal(data, split, high-1);  
	     }  
	}
}

以上为递归算法,当然也有非递归。

 

 

 

今天就写到这,之后再慢慢累积更新。

© 著作权归作者所有

共有 人打赏支持
上一篇: 排序算法总结
下一篇: Mysql索引分析
阿阿阿阿阿局
粉丝 10
博文 48
码字总数 61219
作品 0
成都
私信 提问
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆
2011/12/03
0
0
算法第四版-文字版-下载地址-Robert Sedgewick

下载地址:https://download.csdn.net/download/moshenglv/10777447 算法第四版,文字版,可复制,方便copy代码 目录: 第1章 基 础 ....................... . .............................

老莫offer
11/11
0
0
Python数据结构总结篇

数据结构篇主要是阅读[Problem Solving with Python](http://interactivepython.org/courselib/static/pythonds/index.html)时写下的阅读记录,当然,也结合了部分[算法导论](http://en.wik...

宅男潇涧
2014/07/06
544
0
zg手册 之 python2.7.7源码分析(3)-- list 对象和 dict 对象

list 对象 list 对象的定义 list对象内部是使用数组实现,在数组中存储的是指针,指向要保存的对象。 allocated是list中数组的大小,ob_size是当前已经使用的数组大小。 typedef struct { /...

东昕
2014/08/26
0
0
snort 中的Boyer-Moore

声明 snort中的字串查找,以下代码出自snort-2.9.6.0。是snort中用于字串匹配的底层接口。主要是参考了Boyer-Moore算法进行实现的. 关于Boyer-Moore的文章可以参考: http://my.oschina.net/u...

面码
2014/07/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Confluence 6 快捷键

快捷键图标。 官方的下载地址为:https://atlassianblog.wpengine.com/wp-content/uploads/2018/01/keyboard-shortcuts-infographics.pdf...

honeymose
57分钟前
2
0
Apache限定目录解析PHP,限制user_agent,PHP相关的配置

Apache限定目录解析PHP 配置前访问upload/index.php [root@test-a ~]# curl -x192.168.77.139:80 'www.test.com/upload/index.php'This is upload diretory 配置,/usr/local/apache2.4/......

野雪球
今天
3
0
java.util.Concurrent.Exchanger源码

类图 源码: package java.util.concurrent;import java.util.concurrent.atomic.AtomicInteger;import java.util.concurrent.atomic.AtomicReference;import java.util.concurrent......

狼王黄师傅
今天
6
0
Kubernetes里的secret最基本的用法

Secret解决了密码、token、密钥等敏感数据的配置问题,使用Secret可以避免把这些敏感数据以明文的形式暴露到镜像或者Pod Spec中。 Secret可以以Volume或者环境变量的方式使用。 使用如下命令...

JerryWang_SAP
昨天
5
0
2018-11-20学习笔记

1. python数据类型: 给变量赋值什么样的值,变量就是什么样的类型 给变量赋值整数,变量就是整数类型 给变量赋值字符串,变量就是字符串类型 123 和“123”一样吗? 在python中 单引号 与双...

laoba
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部