文章的最后，小灰遗留了一个问题：

在一个旋转有序数组中，如何查找一个整数呢？

注意这里有一个前提：我们并不直接知道给定数组的旋转点。

如何解决呢？今天让我们来做详细介绍：

是哪三种结果呢？

我们仍然以数组【2，5，7，9，12，14，20，26，30】为例来进行分析：

第一步，我们定位到数组的中位数：

第二步，比较中位数和待查找目标整数之间的大小关系，这时候会出现三种可能性：

1.如果中位数>目标整数，则新的查找区间收缩在【start, mid-1】

2.如果中位数<目标整数，则新的查找区间收缩在【mid+1，end】

3.如果中位数 == 目标整数，则查找成功

（注意：下面的分析会比较烧脑，一次看不明白的小伙伴们可以多看几遍。另外，本文的所有分析都是基于升序数组。）

在分析之前，首先明确一个概念：旋转点。

旋转点是什么呢？我们这里规定，假设旋转有序数组恢复为普通有序数组，位于普通有序数组第一个位置的元素，就是旋转数组的旋转点。

直白地说，旋转点就是旋转数组中最小的元素：

那么，当我们选择中位数，进行一次二分查找的时候，会出现哪些结果呢？仅仅从中位数与旋转点的相对位置来看，有两种结果：

情况A，旋转点在中位数的右侧：

这种情况下有两个特点：

1.中位数以及它左侧的元素，全部是升序的。

2.最左侧元素，必定小于等于中位数。

情况B，旋转点在中位数的左侧，或与中位数重合：

这种情况下有两个特点：

1.中位数以及它右侧的元素，全部是升序的。

2.最左侧元素，必定大于中位数。

上面所分析的，仅仅是从中位数与旋转点的相对位置角度。如果再引入要查找的目标整数呢？上面的情况A和情况B，就会各自分为两种子情况。

首先回过头看看上述的情况A，要查找的目标整数（假设存在）有可能出现在哪里呢？

答案很简单：

1.查找目标在中位数的左侧

由于情况A的中位数左侧是升序区，所以查找目标出现在左侧的条件是：

最左侧元素 <= 查找目标 < 中位数

2.查找目标在中位数的右侧

由于查找目标出现在左侧的条件已经确定，那么出现在右侧的条件判断就简单了：

！（最左侧元素 <= 查找目标 < 中位数）

接下来我们再看看上述的情况B，要查找的目标整数（假设存在）可能出现在哪里呢？

答案也是同样道理：

1.查找目标在中位数的右侧

由于情况B的中位数右侧是升序区，所以查找目标出现在右侧的条件是：

中位数 < 查找目标 <= 最右侧元素

2.查找目标在中位数的左侧

由于查找目标出现在右侧的条件已经确定，那么出现在左侧的条件判断就简单了：

！（中位数 < 查找目标 <= 最右侧元素）

综上，我们总结了旋转数组二分查找可能出现的四种情况

public
static
int
 rotatedBinarySearch
(
int
[]
 array
,
int
 target
){
int
 start 
=
0
,
end
=
 array
.
length
-
1
;
while
(
start
<=
end
)
{
int
 mid 
=
 start 
+
(
end
-
start
)/
2
;
if
(
array
[
mid
]==
target
){
return
 mid
;
}
//情况A：旋转点在中位数右侧
if
(
array
[
mid
]>=
array
[
start
])
{
//最左侧元素 <= 查找目标 < 中位数
if
(
array
[
mid
]>
target 
&&
 array
[
start
]<=
target
){
end
=
 mid 
-
1
;
}
else
{
                start 
=
 mid 
+
1
;
}
}
//情况B：旋转点在中位数左侧，或与中位数重合
else
{
//中位数 < 查找目标 <= 最右侧元素
if
(
array
[
mid
]<
target 
&&
 target
<=
array
[
end
]){
                start 
=
 mid 
+
1
;
}
else
{
end
=
 mid 
-
1
;
}
}
}
return
-
1
;
}
public
static
void
 main
(
String
[]
 args
)
{
int
[]
 array 
=
new
int
[]{
9
,
10
,
11
,
12
,
13
,
1
,
3
,
4
,
5
,
8
};
System
.
out
.
println
(
rotatedBinarySearch
(
array
,
12
));
}