Question

Using Python suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return “The input is not on this list”
You may assume no duplicate exists in the array.
Hint: Use a function. Use the built in method .index( ) and/or for loops.

Answer 1

Step-by-step explanation:

class Solution {

public int search(int[] nums, int target) {

int n = nums.length;

int low = 0 , high = n - 1;

While(low < high){//Set virtual node

int mid = (low + high) / 2;

if(nums[mid] > nums[high]){

low = mid + 1;

}else{

high = mid;

}

}

int rot = low;

low = 0;

high = n - 1;

while(low <= high){

int mid = (low + high) / 2;

Int real = (mid + rot) % n;//The virtual node is mapped to the real node.

if(nums[real] == target){

return real;

}else if(nums[real] < target){

low = mid + 1;

}else{

high = mid - 1;

}

}

return -1;

}

}