二分查找类算法题
程序员文章站
2022-03-08 23:27:52
...
1.假设一个按升序排序的数组在您事先不知道的某个轴上旋转。假如{0,1,2,3,4,5,6,7}可能变为{4,5,6,7,0,1,2},你被给定一个值去搜索,如果找到返回这个值的下标,否则返回-1。假设数组中的数没有重复的,算法复杂度要达到logn.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
思路:
其思想是,当旋转数组时,必须有一半的数组仍按排序顺序排列。
例如,6 7 1 2 3 4 5,顺序从7到1之间的点中断。所以在进行二元搜索时,我们可以判断哪一部分是有序的,目标是否在这个范围内,如果是的话,在那一半继续搜索,如果不是的话,在另一半继续搜索。
public int search(int []nums,int target) {
int start = 0;
int end = nums.length - 1;
while(start <= end) {
int mid = (start + end) /2;
if(nums[mid] == target)
return mid;
if(nums[start] <= nums[mid]) {
if(target < nums[mid] && target >=nums[start])
end =mid - 1;
else start = mid + 1;
}
if(nums[mid] <= nums[end]) {
if(target >nums[mid] &&target <=nums[end])
start = mid +1;
else end = mid -1;
}
}
return -1;
}