文档章节

给定一个排序后的数组,包含n个整数,但这个数组已被旋转过多次,找出数组中的某个元素

一贱书生
 一贱书生
发布于 2016/11/23 09:10
字数 330
阅读 13
收藏 0
点赞 0
评论 0

/**

 * 功能:给定一个排序后的数组,包含n个整数,但这个数组已被旋转过多次,次数不详。找出数组中的某个元素。

 * 可以假定数组元素原先是按从小到大的顺序排列的。

 */

 

  1. /** 
  2.  * 思路:数组被旋转过了,则寻找拐点。 
  3.  * @param a 
  4.  * @param left 
  5.  * @param right 
  6.  * @param x:要搜索的元素 
  7.  * @return 
  8.  */  
  9. public static int search(int[] a,int left,int right,int x){  
  10.     int mid=(left+right)/2;  
  11.     if(x==a[mid])//找到元素  
  12.         return mid;  
  13.     if(left>right)  
  14.         return -1;  
  15.       
  16.     if(a[left]<a[mid]){//左半边为正常顺序  
  17.         if(x>=a[left]&&x<=a[mid]){  
  18.             return search(a,left,mid-1,x);//搜索左半边  
  19.         }else{  
  20.             return search(a, mid+1, right, x);//搜索右半边  
  21.         }  
  22.     }else if(a[mid]<a[right]){//右半边为正常顺序  
  23.         if(x>=a[left]&&x<=a[mid]){  
  24.             return search(a,left,mid-1,x);//搜索左半边  
  25.         }else{  
  26.             return search(a, mid+1, right, x);//搜索右半边  
  27.         }  
  28.     }else if(a[left]==a[mid]){//左半边是重复元素  
  29.         if(a[mid]!=a[right]){//若右边元素不同,则搜索右边  
  30.             return search(a, mid+1, right, x);//搜索右半边  
  31.         }else{//否则两边都搜索  
  32.             int result=search(a, left, mid=1, x);  
  33.             if(result==-1){  
  34.                 return search(a, mid+1, right, x);  
  35.             }else  
  36.                 return result;  
  37.         }  
  38.     }  
  39.     return -1;  

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 0
1111111111111 算法汇总

如何找到两个相交链表对交点? 如果两个单向链表有公共节点,则两个链表会构成Y型结构,最后一个节点相同 我们可以从头开始遍历两个链表,找到最后一个节点的指针,设为pa,pb。同时记录下两...

素雷 ⋅ 01/03 ⋅ 0

找出数组中两数之和为指定值的所有整数对

一,问题描述 给定一个整型数组(数组中的元素可重复),以及一个指定的值。打印出数组中两数之和为指定值的 所有整数对 思路1:可以用hash表来存储数组中的元素,这样我们取得一个数后,去判...

一贱书生 ⋅ 2016/11/28 ⋅ 0

查找算法总结

查找算法:顺序查找、二分查找、分块查找、二叉查找树、B树、B+树 一、二分查找(常规) 题目描述: (牛客网http://www.nowcoder.com/practice/28d5a9b7fc0b4a078c9a6d59830fb9b9?rp=1&ru=/...

阿阿阿阿阿局 ⋅ 2016/07/28 ⋅ 0

Lintcode61 Search for a Range solution 题解

【题目描述】 Given a sorted array of n integers, find the starting and ending position of a given target value.If the target is not found in the array, return [-1, -1]. 给定一个......

Winnielyn ⋅ 2017/08/26 ⋅ 0

算法编程题

1、 题目描述 对于一个字符串,请设计一个高效算法,找到第一次重复出现的字符。 给定一个字符串(不一定全为字母)A及它的长度n。请返回第一个重复出现的字符。保证字符串中有重复字符,字符串...

tomcater ⋅ 2016/07/05 ⋅ 3

玩转算法面试:(四)LeetCode查找类问题

查找问题 两类查找问题 查找有无:元素’a’是否存在?set;集合 查找对应关系(键值对应):元素’a’出现了几次?map;字典 通常语言的标准库中都内置set和map 容器类 屏蔽实现细节 了解语...

天涯明月笙 ⋅ 2017/09/21 ⋅ 0

Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛 ⋅ 2017/11/10 ⋅ 0

算法知识梳理(4) - 数组第一部分

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 一、概要 本文介绍了有...

泽毛 ⋅ 2017/11/10 ⋅ 0

数据结构与算法面试题80道

1.把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / 6 14 / / 4 8 12 16 转换成...

_子墨 ⋅ 2014/10/22 ⋅ 0

微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai ⋅ 2012/08/05 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

windows profesional 2017 build problem

.net framework .... https://stackoverflow.com/questions/43330915/could-not-load-file-or-assembly-microsoft-build-frameworkvs-2017...

机油战士 ⋅ 42分钟前 ⋅ 0

python3中报错的解决方法(长期更新)

1、ImportError: No module named ‘DjangoUeditor’ 出错原因:安装DjangoUeditor库适用于python2,需要下载适用python3的 下载地址:https://github.com/twz915/DjangoUeditor3 2、python3......

xiaoge2016 ⋅ 47分钟前 ⋅ 0

数据结构与算法之双向链表

一、双向链表 1.双向链表的结点结构 typedef struct DualNode{ ElemType data; struct DualNode *prior; // 前驱结点 struct DualNode *next; // 后继结点}DualNode, *DuL...

aibinxiao ⋅ 今天 ⋅ 0

五大最核心的大数据技术

大数据技术有5个核心部分,数据采集、数据存储、数据清洗、数据挖掘、数据可视化。关于这5个部分,有哪些核心技术?这些技术有哪些潜在价值?看完今天的文章就知道了。 大数据学习群:7165810...

董黎明 ⋅ 今天 ⋅ 0

PhpStorm 头部注释、类注释和函数注释的设置

首先,PhpStorm中文件、类、函数等注释的设置在:setting-》Editor-》FIle and Code Template-》Includes下设置即可,其中方法的默认是这样的: /**${PARAM_DOC}#if (${TYPE_HINT} != "v...

nsns ⋅ 今天 ⋅ 0

spring.net AOP

http://www.springframework.net/doc-latest/reference/html/aop-quickstart.html https://www.cnblogs.com/wujy/archive/2013/04/06/3003120.html...

whoisliang ⋅ 今天 ⋅ 0

【HAVENT原创】创建 Dockerfile 生成新的镜像,并发布到 DockerHub

注意:Win7 与 Win10 的版本存在差异,Win7 版本使用 Docker Quickstart Terminal 进入控制台,Win10下面直接用管理员权限打开控制台或者 PowerShell 即可;另外 Win7 下面只能访问 C盘,/ap...

HAVENT ⋅ 今天 ⋅ 0

pom.xml出现web.xml is missing ...解决方案

提示信息应该能看懂。也就是缺少了web.xml文件,<failOnMissingWebXml>被设置成true了。 搜索了一下,Stack Overflow上的答案解决了问题,分享一下。 目前被顶次数最多的回答原文如下: This...

源哥L ⋅ 今天 ⋅ 0

js时间戳与日期格式之间相互转换

1. 将时间戳转换成日期格式 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // 简单的一句代码 var date = new Date(时间戳); //获取一个时间对象 /** 1. 下面是获取时间日期的方法,需要什么样的格式自己...

Jack088 ⋅ 今天 ⋅ 0

web添加log4j

添加xml配置log4j.properties # Global logging configuration---root日志设置#log4j.rootLogger=info,dailyRollingFile,stdoutlog4j.rootLogger=debug,stdout,dailyRollingFile---......

黄柳淞 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部