方法1.例如4，5，6，7，0，1，2
? ? 首先取中間值，取完中間值之后左右總有一邊的是升序的排列，判斷target的值是否在這個序列里面，
如果在，直接在這個序列里做二分查找，如果不在，則繼續(xù)在另外的序列做上訴的判斷。
時間復雜度：O(logn).
注意：主要是要時刻注意臨界值，什么時候跳出循環(huán)要把握好，否則可能陷入死循環(huán)。
這道題主要是考驗了對二分查找的運用。
class Solution {
? ? public int search(int[] nums, int target) {
? ? ? ? int mid;
? ? ? ? int start=0,end=nums.length-1;
? ? ? ? int count=-1;
? ? ? ? while(start<=end){
? ? ? ? ? ? mid=(start+end)/2;
? ? ? ? ? ? if(target==nums[mid]){
? ? ? ? ? ? ? ? count=mid;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? if(nums[start]<=nums[mid]){
? ? ? ? ? ? ? ? if(target>=nums[start]&&target<=nums[mid]){
? ? ? ? ? ? ? ? ? ? end=mid-1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else{
? ? ? ? ? ? ? ? ? ? start=mid+1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? if(target>=nums[mid]&&target<=nums[end]){
? ? ? ? ? ? ? ? ? ? start=mid+1;
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? end=mid-1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return count;
? ? }
}
方法2：先用二分法找到最小值的坐標，然后再進行二分。
class Solution {
? ? public int search(int[] nums, int target) {
? ? ? ? int start=0,end=nums.length-1;
? ? ? ? int mid;
? ? ? ? //先找到最小的值的坐標
? ? ? ? while(start<end){
? ? ? ? ? ? mid=(start+end)/2;
? ? ? ? ? ? if(nums[mid]>nums[end]){
? ? ? ? ? ? ? ? start=mid+1;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? end=mid;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int min=end;
? ? ? // System.out.println(min);
? ? ? ? if(nums.length==0){
? ? ? ? ? ? return -1;
? ? ? ? }
? ? ? ? if(target>=nums[0]&&min>0&&target<=nums[min-1]){
? ? ? ? ? ? return binaryFind(0,min-1,nums,target);?
? ? ? ? }
? ? ? ? if(target>=nums[min]&&target<=nums[nums.length-1]){
? ? ? ? ? ? return binaryFind(min,nums.length-1,nums,target);
? ? ? ? }
? ? ? ? return -1;
? ? }
? ? public int binaryFind(int start,int end,int[] nums,int target){
? ? ? ? int mid;
? ? ? ? while(start<=end){
? ? ? ? ? ? ? ? mid=start+(end-start)/2;
? ? ? ? ? ? ? ? if(nums[mid]==target){
? ? ? ? ? ? ? ? ? ? return mid;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if(target>nums[mid]){
? ? ? ? ? ? ? ? ? ? start=mid+1;
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? end=mid-1;
? ? ? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return -1;
? ? }
}
