分析一:
给定一个循环无重复有序数组,如12345 ->34512,查找给定数值target在数组中的下标,如没有则返回-1。
循环递增数组有这么一个性质:以数组中间元素将循环递增数组划分为两部分,则一部分为一个严格递增数组,而另一部分为一个更小的循环递增数组。
当中间元素大于首元素时,前半部分为严格递增数组,后半部分为循环递增数组;当中间元素小于首元素时,前半部分为循环递增数组;后半部分为严格递增数组。
分析二:
对于一个数组4,5,6,7,0,1,2 你首先找到那个转折点,就是大于下一个相邻数字的那个数字的下标,在这个数组就是数字7的下标3。
步骤:
1 找到转折点下标,把数组分成两个有序的子数组
2 如果转折点下标返回-1,意思是数组有序,可以直接在整个数组中查找
3返回不是-1,数组是旋转后的数组。 如果target大于等于第一个元素即A[0],那就在左半部分数组中查找,如果target小于A[0],那就在右半部分中寻找