文档章节

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

一贱书生
 一贱书生
发布于 2016/11/23 09:10
字数 330
阅读 98
收藏 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;  

© 著作权归作者所有

一贱书生
粉丝 21
博文 723
码字总数 600123
作品 0
私信 提问
加载中

评论(0)

程序员面试金典 - 面试题 10.03. 搜索旋转数组(二分查找)

1. 题目 搜索旋转数组。给定一个排序后的数组,包含n个整数,但这个数组已被旋转过很多次了,次数不详。 请编写代码找出数组中的某个元素,假设数组元素原先是按升序排列的。若有多个相同元素...

Michael阿明
04/04
0
0
Go程序员面试算法宝典-读后感1

这本书是讲解Go语言程序员面试笔试真题的书籍,讲的还不错,值得一看。 计算机技术博大精深,日新月异………………大神们疯狂的更新着技术,(我就更新,不服打我呀)虽然换汤不换药,又有几...

osc_z97fe7xu
2019/06/19
30
0
TypeScript实现数组相关简单算法

算法(algorithm),在数学(算学)和计算机科学之中,为任何良定义的具体计算步骤的一个序列,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包...

MarkMan
2018/09/11
0
0
leetcode 一些算法题及答案

两数之和 给定一个整数数组 和一个目标值 ,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样...

osc_w6kvmckv
2019/02/28
4
0
leetcode|初级算法-数组

01 起 最近“不务正业地”刷了一波leetcode上的算法题,初级算法已经刷完50%,战况如下, 刷题固然爽快,但及时总结才是进步之道,下面就数组部分的题目进行回顾和总结。 注意,刷题使用的语...

邓莎
2018/09/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot 整合 Redis 缓存

1.首先导入使用Maven导入jar包 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-data-redis</artifactId></dependency><......

FH-Admin
31分钟前
12
0
如何安装WordPress插件 - 初学者的分步指南 - WP站长

<!-- wp:paragraph -->安装WordPress后,每一个初学者需要学习的第一件事就是如何安装WordPress插件。插件允许您向WordPress添加新功能,例如添加图库、幻灯片等。有数千个可用于WordPress的...

wpzhanzhang
46分钟前
8
0
【Flutter组件终结篇】332个组件 658页PDF

老孟导读:历时1年的时间,整理完成了330+组件的详细用法,不仅包含UI组件,还包含了功能性的组件。 虽然整理了 330+的组件基本用法,但并不是让你每一个都学习一遍,任何技术基本都是掌握 ...

老孟Flutter
今天
17
0
三星手机又中招:一张壁纸可引发系统崩溃 附临时解决方法

  前几天国内有大量用户发现三星手机崩溃、黑屏或者无限重启, 这可能是三星手机的日历 APP 的 bug。这件事还没完,三星手机今天又发现了新的问题,换上一张特别的壁纸就会导致系统崩溃,不...

alkcendkljk
今天
13
0
查找当前目录和文件目录[重复] - Find current directory and file's directory [duplicate]

问题: This question already has answers here : 这个问题已经在这里有了答案 : How to properly determine current script directory? 如何正确确定当前脚本目录? (11 answers) (11个答...

技术盛宴
今天
27
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部