文档章节

查找算法总结

阿阿阿阿阿局
 阿阿阿阿阿局
发布于 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);  
	     }  
	}
}

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

 

 

 

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

© 著作权归作者所有

共有 人打赏支持
阿阿阿阿阿局
粉丝 10
博文 48
码字总数 61219
作品 0
成都
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

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

索隆
2011/12/03
0
0
Python数据结构总结篇

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

宅男潇涧
2014/07/06
544
0
为什么 GNU grep 如此之快?

编注:这是GNU grep的原作者Mike Haertel 在FreeBSD邮件列表中对 “GNU grep为什么比BSD grep要快” 所做的回答,下面是邮件正文内容: Gabor 您好, 我是GNU grep的原作者,同时也是一名Fre...

oschina
2013/12/05
5.5K
31
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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

nginx模块学习六 add_header 跨域访问

语法 Syntax: add_header name value [always];Default: --Context:http,server,location,if in location 例:/etc/nginx/conf.d/default.conf server {    listen       80; ......

Romanceling
今天
0
0
SpringBoot初探

#SpringBoot初探 三种创建SpringBoot项目的方式: 第一种:使用IDEA创建maven项目,选择maven-archetype-quickstart; 第二种:使用IDEA创建Spring Initializer,选择web组件; 第三种:使用...

向码而生
今天
2
0
IO

JAVA中IO技术:BIO、NIO、AIO 1、同步异步、阻塞非阻塞概念 同步和异步是针对应用程序和内核的交互而言的。 阻塞和非阻塞是针对于进程在访问数据的时候,根据IO操作的就绪状态来采取的不同方...

DemonsI
今天
0
0
org.apache.commons 常用工具类

一. org.apache.commons.io.IOUtils closeQuietly 关闭一个IO流、socket、或者selector且不抛出异常。通常放在finally块。 toString 转换IO流、 Uri、 byte[]为String。 copy IO流数据复制,...

sprouting
今天
0
0
linux使用Inotify监控目录或者文件状态变更

基本概念: Inotify 是一个 Linux特性,它监控文件系统操作,比如读取、写入和创建。Inotify 反应灵敏,用法非常简单,并且比 cron 任务的繁忙轮询高效得多。 需求: 1.有一个文件采集进程,...

mickelfeng
今天
0
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部