欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找类算法题

程序员文章站 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;
   }
相关标签: 二分查找类