题目描述：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
（ 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:

  1. 输入: nums = [4,5,6,7,0,1,2], target = 0
  2. 输出: 4

示例 2:

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

算法实现：

JavaScript

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number}
  5.  */
  6. var search = function(nums, target) {
  7.     if (nums.length === 0) {
  8.         return -1
  9.     }
  10.     var p = (start, end) => {
  11.         if (nums[start] === target) {
  12.             return start
  13.         }
  14.         if (nums[end] === target) {
  15.             return end
  16.         }
  17.         if (start === end || start === end - 1) {
  18.             return -1
  19.         }
  20.         var mid = Math.floor((start + end) / 2)
  21.         if (nums[mid] === target) {
  22.             return mid
  23.         }
  24.         if (nums[mid] > nums[start]) {
  25.             if (target > nums[start] && target < nums[mid]) {
  26.                 return p(start, mid)
  27.             } else {
  28.                 return p(mid, end)
  29.             }
  30.         } else {
  31.             if (target > nums[mid] && target < nums[end]) {
  32.                 return p(mid, end)
  33.             } else {
  34.                 return p(start, mid)
  35.             }
  36.         }
  37.     }
  38.     return p(0, nums.length - 1)
  39. };

不考虑时间复杂度

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number}
  5.  */
  6. var search = function(nums, target) {
  7.     for (var i = 0; i < nums.length; i++ ) {
  8.         if (target === nums[i]) {
  9.             return i
  10.         }
  11.     }
  12.     return -1
  13. };

思考：

考察二分查找，重点在于考虑倒序的位置在mid之前还是mid之后。

总结：

对于二分查找的方法还需要进一步熟悉，现在还不能做到完全独立完成题目。