文档章节

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

一贱书生
 一贱书生
发布于 2016/11/23 09:10
字数 330
阅读 19
收藏 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
博文 724
码字总数 600123
作品 0
私信 提问
TypeScript实现数组相关简单算法

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

MarkMan
09/11
0
0
leetcode|初级算法-数组

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

邓莎
09/05
0
0
LeetCode基础算法-数组

LeetCode基础算法-数组 算法 LeetCode 数组相关 1. 从排序数组中删除重复项 描述: 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 ...

24K男
09/06
0
0
1111111111111 算法汇总

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

素雷
01/03
0
0
找出数组中两数之和为指定值的所有整数对

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

一贱书生
2016/11/28
35
0

没有更多内容

加载失败,请刷新页面

加载更多

深入解析ES6之数据解构的用法

本文介绍了深入理解ES6之数据解构的用法,写的十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批评指正。 一 对象解构 对象解构语法在赋值语句的左...

前端攻城老湿
8分钟前
3
0
芯片原理和量子力学

很多文盲觉得量子力学只是一个数学游戏,没有应用价值,呵呵,下面咱给计算机芯片寻个祖宗,请看示范: 导体,咱能理解,绝缘体,咱也能理解,小盆友们第一次被物理整懵的,怕是半导体了,所...

天王盖地虎626
8分钟前
1
0
Django model update的各种用法介绍

Django model update的各种用法介绍 model update常规用法 假如我们的表结构是这样的: class User(models.Model): username=models.CharField(max_length=255,unique=True,verbose_na......

_Change_
11分钟前
1
0
Frost & Sullivan权威报告:阿里云再次领跑云WAF大中华区市场

近日,国际权威分析机构Frost & Sullivan 针对Web应用防火墙(简称“WAF”)领域发布了《2017年亚太区Web应用防火墙市场报告》,阿里云以市场占有率45.8%的绝对优势连续两年领跑大中华区云WAF...

阿里云官方博客
16分钟前
0
0
Java程序员可知为何公司宁花25K重新招人,也不花20K留住老员工?

身在职场,经常会暗自打听同事工资,尤其是得知身边新入职同事的工资居然比自己高,还高出一大截时,心里自然很不平衡,一心想要离职。 那么,为什么公司宁愿花高价招聘新员工也不愿意给老员...

Java填坑路
22分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部