Searching

Question 1

Binary Search mid split

Answer 1

Remember to split into BS(left,mid-1) and BS(mid+1,right) since the base check already checks if arr[mid] == key.

Question 2

Find Majority Element

Answer 2

To find majority, first find a candidate for majority by Moore’s Voting Algorithm.

1. Set index=0 and count=1 and check if A[i] == A[idx]
2. if true, then increase count else decrease.
3. If count becomes 0, then set idx = i and count=1

Finally, check if the candidate is indeed the majority element. if count > N//2: return A[idx]

Question 3

Peak element in sorted rotated array

Answer 3

[10 20 30 40 1 2]

Apply binary search. Check A[mid] wrt any corner element. If A[mid] > A[left] then pivot lies on right and vice-versa.

Question 4

Peak element in unsorted array

Answer 4

[10 20 15 5 23 90 67]
A corner element is also a peak if it is larger than its neighboring element.
Apply binary search. compare mid wrt its left and right.
If left or right is greater than move towards the greater side since peak element will lie in that direction. If both are greater, then peak lies in both direction. In that case, you may pick either.

Question 5

Search key in an infinite sorted array

Answer 5

Binary search. First find the right index to work with by search from i=1 while(A[i] < key): i=i*2. (Check A[0] == key).
check if A[i] == key return i.
Then you can apply binary search between i/2 to i.

Question 6

Find Square Root

Answer 6

if not perfect square return floor of sqrt. eg 5 -> 2. To find sqrt of x:
mid = l + (r-l)//2
sqrt = x//mid

if mid == sqrt or (mid < sqrt and ((mid+1) > x//(mid+1))):
return mid