GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 28

Answer 1

As it is a divide and conquer approach, the first thought of applying binary search comes to mind and definitely it works here,

let me explain.

Consider an array of having 0’s followed by 1’s and we apply binary search over this, after finding the middle index just check its previous index value and its next index value.

if both are 0 then move to upper half of sub array

if both are 1 then move to lower half of sub array

and finally if previous is 0 and next is 1 that the transition index

So the overall process is same as binary search hence its time complexity is theta(log n)  Hence the correct option is A

Comments

nicely explained :)

---

can we also say that ,we just compare if mid is 0 then we need to check right subarray as transition index cannot be on the left side and if mid is 1 then transition index must be lying in the left subarray !

---

The method which u have putforward will not be able to find the transition index like where does the value of 0 changes to 1 couldn't be known so only we need to check the previous and next bit of the mid value to say here the transition happens, hope u got the point