给定一个排序后的数组,包含n个整数,但这个数组已被旋转过多次,找出数组中的某个元素
给定一个排序后的数组,包含n个整数,但这个数组已被旋转过多次,找出数组中的某个元素
一贱书生 发表于1年前
给定一个排序后的数组,包含n个整数,但这个数组已被旋转过多次,找出数组中的某个元素
  • 发表于 1年前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

/**

 * 功能:给定一个排序后的数组,包含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;  
共有 人打赏支持
粉丝 15
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: