文档章节

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

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

没有更多内容

加载失败,请刷新页面

加载更多

打包QML程序

1、windeployqt执行路径(D:\Qt\5.12.0\msvc2017_64\bin)加入到PATH中 2、使用Qt自带的命令行交互 Command 终端(Qt 5.12.0 64-bit for Desktop (MSVC 2017))切换到 Release 编译成功的exe...

渣渣曦
42分钟前
3
0
优秀互联网高级测试工程师应该具备的能力

概述 在之前写的互联网高级测试工程师至少具备的能力一文中,提到了测试工程师至少具备的能力,但是并没有提到优秀测试工程师应该具备的能力,下文简单的谈一谈。当然这些全部都是我的个人理...

Sam哥哥聊技术
46分钟前
4
0
webpack项目配置

前端工程化 前端工程化是根据业务特点,将前端开发流程规范化,标准化,它包括了开发流程、技术选型、代码规范、构建发布等等,用语提升前端工程师的开发效率和代码质量。 自动化构建工具 1、...

羊皮卷
49分钟前
1
0
Linux命令备忘录: jobs 显示Linux中的任务列表及任务状态命令

jobs命令用于显示Linux中的任务列表及任务状态,包括后台运行的任务。该命令可以显示任务号及其对应的进程号。其中,任务号是以普通用户的角度进行的,而进程号则是从系统管理员的角度来看的...

开元中国2015
今天
4
0
springboot Whitelabel Error Page(Not Found)解决方案

当出现上图图的错误时注意 报错信息 There was an unexpected error (type=Not Found, status=404). Not Found代表未访问到资源 解决方案:比较访问路径和代码的路径有没有写错 正确的访问路...

斩神魂
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部