search

zouyingjie / arts

arts practice
27 stars 2 forks source link

arts/2018-07-29.md中A的疑问 #1

Open keeprunway opened 6 years ago

keeprunway commented 6 years ago

arts/2018-07-29.md 中A，你改进以后，getPivot pivot = min + ((max - min) >> 1); 是什么含义？是/2 么？getPivot相当于二分查找Root？

个人认为题目中说的旋转，其实算是对数组进行了一次切分，而且数组中指明了是升序，那么切分以后，nums[0]是一定大于nums[size-1]的。

zouyingjie commented 6 years ago
  1. pivot = min + ((max - min) >> 1); 是什么含义？ 是/2 么 是的
  2. getPivot 找到数组最小值的位置，通过这个我们可以知道要查找的值的索引范围

nums[0]是一定大于nums[size-1] 这个是没问题的。本来 0 - n 的升序数组，现在变为了 0-(m-1)，m-n 两部分升序数组，并且 0 - (m-1) 中的值是大于 m-n 中的值的，这里需要确定要查找的值是在 0 - (m-1) 中还是 m-n 部分中，找到后在通过二分查找拿到对应的 index。