leetcode 33. Search in Rotated Sorted Array(二分查找）

本文主要是介绍leetcode 33. Search in Rotated Sorted Array(二分查找），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

只要找到枢轴，在左边或者右边查找target，因为是有序的，所以使用二分查找，这里实现了递归和非递归两种二分查找：

/*int binarySearch(int *nums,int left,int right,int target)   //递归的
{int mid;if(left>=right){if(nums[left]==target)return left;else if(nums[right]==target)return right;elsereturn -1;}else{mid=(left+right)/2;if(target>nums[mid]){mid++;return binarySearch(nums,mid,right,target);}else if(target<nums[mid]){mid--;return binarySearch(nums,left,mid,target);}elsereturn mid;}
}*/int binarySearch(int *nums,int left,int right,int target)  //非递归的方法
{int mid;while(left<=right){if(nums[left]==target)return left;else if(nums[right]==target)return right;else{mid=(left+right)/2;if(target>nums[mid]){mid++;left=mid;}else if(target<nums[mid]){mid--;right=mid;}elsereturn mid;}}return -1;
}int search(int* nums, int numsSize, int target) {int i;if(nums[0]<=nums[numsSize-1])  //没有经过旋转return binarySearch(nums,0,numsSize-1,target);else{int pivot=0;for(i=0;i<=numsSize-2;i++){if(nums[i]>nums[i+1]){pivot=i;break;}}if(target<=nums[numsSize-1]&&target>=nums[pivot+1]){return binarySearch(nums,pivot+1,numsSize-1,target);}else if(target>=nums[0]&&target<=nums[pivot]){return binarySearch(nums,0,pivot,target);}elsereturn -1;}}

这篇关于leetcode 33. Search in Rotated Sorted Array(二分查找）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---