# Require admin to update test cases

• I think it's necessary to update test cases. The reason is as follows:

when I easily try to find the target one by one in the array and it's a O(n) algorithm, it costs 4ms,
the O(n) solution:

``````class Solution {
public:
int search(vector<int>& nums, int target) {
for(int i=0; i<nums.size(); i++)
if(nums[i] == target)
return i;
return -1;
}
};
``````

however, when I first find the min index using binary search, and search the target using binary search again, which is a O(lgn) algorithm, it costs 12ms!
the O(logn) solution:

``````class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.size()==0)
return -1;

int p = min_index(nums);
if(target < nums[p] || target > nums[p==0?(nums.size()-1):(p-1)])
return -1;
if(p==0)
{
return binary_search(nums, 0, nums.size()-1, target);
}
if(target == nums[nums.size()-1])
return nums.size()-1;
else if(target < nums[nums.size()-1])
return binary_search(nums, p, nums.size()-1, target);
else
return binary_search(nums, 0, p-1, target);
}

int binary_search(vector<int> &v, int left, int right, int val)
{
while(left<=right) {
int m = (left+right)/2;
if(v[m] == val)
return m;
if(v[m] > val)
right = m-1;
else
left = m+1;
}
return -1;
}

int min_index(vector<int> &nums)
{
int left = 0, right = nums.size()-1;
while(left <= right) {
if(nums[left] < nums[right])
return left;

int mid = (left+right)/2;
if(nums[mid] > nums[left])
left = mid;
else if(nums[mid] < nums[left])
right = mid;
else {
return nums[left] < nums[right] ? left:right;
}
}
}
};``````

• It make sense, O(N) runtime is not necessary longer than O(logN), It is necessary only when N is infinite.

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