educative.io

Search in a Rotated Array Incorrect TestCase and Solution#2

Courses
,
#1

For some test cases, the brute force way won’t pass. Only use the modified binary search will pass all the test cases. For example:
searchRotatedArray([5,5,5,5,5,5,5],0,6,)5

The expected output is 3 which does not really make sense because the first index matches the target is 0. If the requirement is asking for the last index mataches the target, the index should be 5. None gives 3.

Course: https://www.educative.io/collection/10370001/5347133077061632
Lesson: https://www.educative.io/collection/page/10370001/5347133077061632/5094816851427328

#2

Hi @Manxiang_Zhang,

Thank you for reaching out to the Educative team.

The algorithm is constructed in such a way that it starts by finding the target from the middle index. The algorithm specifically mentions that “If the element at the middle is equal to the element being searched for, return the middle index”. The binary search algorithm firsts checks if the middle element is the target. if yes, it returns the index of that middle element. The expected output of 3 is due to the way the algorithm is structured.

I hope it helps. Happy Learning :blush: