An O(logn) C++ solution


  • 0
    5
    int search(vector<int>& nums, int target) {
    	int begin = 0, end = nums.size() - 1, mid;
    	while (begin <= end) {
    		mid = (begin + end) >> 1;
    		if (target < nums[mid]) {
    			if (nums[begin] < nums[end] || nums[mid] < nums[begin] || target > nums[end]) {
    				end = mid - 1;
    			} else {
    				begin = mid + 1;
    			}
    		} else if (target > nums[mid]) {
    			if (nums[begin] < nums[end] || nums[mid] > nums[begin] || target < nums[begin]) {
    				begin = mid + 1;
    			} else {
    				end = mid - 1;
    			}
    		} else {
    			return mid;
    		}
    	}
    	return -1;
    }

Log in to reply
 

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