>>分享数据结构和算法相关的知识和技术 书籍支持  卫琴直播  品书摘要  在线测试  资源下载  联系我们
发表一个新主题 开启一个新投票 回复文章 您是本文章第 19789 个阅读者 刷新本主题
 * 贴子主题:  小米面试算法题:搜索旋转排序数组 回复文章 点赞(0)  收藏  
作者:flybird    发表时间:2020-03-08 19:29:10     消息  查看  搜索  好友  邮件  复制  引用

                                                                                                

小米面试算法题:搜索旋转排序数组

题目描述

     假设有一个排序的按未知的旋转轴旋转的数组(比如, 0 1 2 4 5 6 7 可能成为 4 5 6 7 0 1 2)。给定一个目标值进行搜索,如果在数组中找到目标值返回数组中的索引位置,否则返回-1。你可以假设数组中不存在重复的元素。                          

样例

     例1:        

  1.      输入: [ 4,  5,  1,  2,  3]  and target= 1,
  2.      输出:  2.

       例2:        

  1.      输入: [ 4,  5,  1,  2,  3]  and target= 0,
  2.      输出:  -1.

题解

     应用二分法分类讨论。

     注意一下分类的细节即可。        

  1.       public   class  Solution {
  2.            public  int  search ( int[] A,  int target) {
  3.               if (A ==  null || A.length ==  0) {
  4.                   return - 1;
  5.              }
  6.               int start =  0;
  7.               int end = A.length -  1;
  8.               int mid;
  9.               while (start +  1 < end) {
  10.                  mid = start + (end - start) /  2;
  11.                   if (A[mid] == target) {
  12.                       return mid;
  13.                  }
  14.                   if (A[start] < A[mid]) {
  15.                       // situation 1, red line
  16.                       if (A[start] <= target && target <= A[mid]) {
  17.                          end = mid;
  18.                      }  else {
  19.                          start = mid;
  20.                      }
  21.                  }  else {
  22.                       // situation 2, green line
  23.                       if (A[mid] <= target && target <= A[end]) {
  24.                          start = mid;
  25.                      }  else {
  26.                          end = mid;
  27.                      }
  28.                  }
  29.              }  // while
  30.               if (A[start] == target) {
  31.                   return start;
  32.              }
  33.               if (A[end] == target) {
  34.                   return end;
  35.              }
  36.               return - 1;
  37.          }
  38.      }

----------------------------
原文链接:https://blog.csdn.net/JiuZhang_ninechapter/article/details/104678863
作者:九章算法

程序猿的技术大观园:www.javathinker.net



[这个贴子最后由 flybird 在 2020-03-08 23:03:06 重新编辑]
  Java面向对象编程-->Java语言中的修饰符
  JavaWeb开发-->访问数据库(Ⅰ)
  JSP与Hibernate开发-->映射一对多关联关系
  Java网络编程-->对象的序列化与反序列化
  精通Spring-->创建综合购物网站应用
  Vue3开发-->Vue简介
  位运算指南
  算法学习与收集:一些有用的算法网站和网页
  对simhash算法的一些思考
  浅谈算法,一些感悟
  银行家算法范例
  活动安排问题(贪心算法)
  基于JavaScript的Base64编码、解码算法
  有趣的位图排序算法
  LRU算法的简单实现范例
  微软面试题:买卖股票的最佳时机
  字节跳动面试官这样问消息队列:分布式事务、重复消费、顺序...
  LinkedList,LinkedHashMap,LruCache源码解析
  谷歌面试算法题:两个排序数组的中位数
  数据结构中的数组
  浅谈常见的七种加密算法及实现
  更多...
 IPIP: 已设置保密
树形列表:   
1页 0条记录 当前第1
发表一个新主题 开启一个新投票 回复文章


中文版权所有: JavaThinker技术网站 Copyright 2016-2026 沪ICP备16029593号-2
荟萃Java程序员智慧的结晶,分享交流Java前沿技术。  联系我们
如有技术文章涉及侵权,请与本站管理员联系。