题目描述
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
题目大意
假设一个已排序的数组在事先未知的某个枢轴处旋转。
（即，0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2）。
给定要搜索的目标值，如果在数组中找到则返回其索引，否则返回-1。
假设数组中不存在重复值。
思路
暴力破解
循环遍历整个数组，找到即返回索引号，找不到就返回-1。
二分查找
- 先判断是否发生旋转，判断旋转的依据就是数组的第一个值大于最后一个值。
- 如果没有发生旋转，直接用二分查找
- 如果发生了旋转，找出旋转点，确定了两个有序的子数组，然后在有序的子数组中进行二分查找。while循环结束，begin对应的是最大值，end对应的是最小值。
代码
暴力破解
int search(int A[], int n, int target)
{
for(int i=0; i<n; i++)
{
if(A[i] == target)
{
return i;
}
}
return -1;
}
运行结果
二分查找
以上。
