My solotion for the question,4ms time,note in chinese


  • 0
    H
    int search(vector<int>& nums, int target){
    	int start=0,end=nums.size()-1,mid;
    	if(nums[start]==target)
    		return start;
    	if(nums[end]==target)
    		return end;
    	while(start<end)
    	{
    		mid=(start+end)/2;
    		cout<<"nums[mid] is:"<<nums[mid]<<endl;
    		if(nums[start]<nums[mid])//前半部分为升序
    		{
    			cout<<"qian"<<endl;
    			if(nums[mid]==target)//刚好等于目标
    				return mid;
    			else if(target>=nums[start] && target<=nums[mid])//小于中间,前半部分又是升序,就定位在前半部分,退出用二分查找
    			{
    				end=mid;
    			    break;
    			}else{////大于中间,不在前半部分
    				start=mid;
    				continue;
    			}
    		}
    		else{///前半部分不是升序,那后半部分一定是升序
    			cout<<"hou"<<endl;
    			if(nums[mid]==target)
    				return mid;
    			else if(target>=nums[mid] && target<=nums[end])
    			{
    				start=mid;
    				break;
    			}
    			else{
    				end=mid;
    				continue;
    			}
    		}
    	}
    	cout<<"start is:"<<start<<" end is:"<<end<<endl;
    	while(start<end)
    	{
    		mid=(start+end)/2;
    		if(mid==start)
    		{
    			if(nums[mid]==target) return mid;
    			mid=end;
    			break;
    		}
    		if(nums[mid]==target)
    			return mid;
    		else if(nums[mid]<target)
    		{
    			start=mid;
    		}
    		else end=mid;
    	}
    	if(nums[mid]==target) return mid;
    	return -1;
    }

  • 0
    H

    i may not make right use of the binary search,if you have any advice ,please email me


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.