# 搜索旋转数组

搜索旋转数组

搜索旋转数组。给定一个排序后的数组,包含n个整数,但这个数组已被旋转过很多次了,次数不详。请编写代码找出数组中的某个元素,假设数组元素原先是按升序排列的。若有多个相同元素,返回索引值最小的一个。

示例1:
 输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
 输出: 8(元素5在该数组中的索引)

示例2:
 输入:arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
 输出:-1 (没有找到)

提示:
 arr 长度范围在[1, 1000000]之间
1
2
3
4
5
6
7
8
9
10
11
12

# 二分法

参考

// 只需要注意: 若有多个相同元素,返回索引值最小的一个
// 多次旋转毫无意义
function search(arr, target) {
  let len = arr.length
  let left = 0
  let right = len - 1

  while(left <= right) {
    // 重点1:当left符合时直接返回, 因为找的是最小的索引
    if (arr[left] === target) {
      return left
    }
    let mid= Math.floor((left+right) / 2)
    // 重点2:当中间值等于目标值,将右边界移到中间,因为左边可能还有相等的值
    if (arr[mid] === target) {
      right = mid
    } else if (arr[0] < arr[mid]) {
      if (arr[0] <= target && target < arr[mid]) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    } else if (arr[0] > arr[mid]) {
      if (arr[mid] < target && target <= arr[len - 1]) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    } else {
      // 重点3:当中间数字与左边数字相等时,将左边界右移
      left += 1
    }
  }

  return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36