SORTING IN LINEAR TIME,

#1

How to do this question using Binary Search?

#2

@CODER_JATIN, this question does’nt uses binary search instead this question is the application of two pointers paradigm,

The solution to this algorithm will require 3 pointers to iterate throughout the array, swapping the necessary elements.

(1) Create a low pointer at the beginning of the array and a high pointer at the end of the array.
(2) Create a mid pointer that starts at the beginning of the array and iterates through each element.
(3) If the element at arr[mid] is a 2, then swap arr[mid] and arr[high] and decrease the high pointer by 1.
(4) If the element at arr[mid] is a 0, then swap arr[mid] and arr[low] and increase the low and mid pointers by 1.
(5) If the element at arr[mid] is a 1, don’t swap anything and just increase the mid pointer by 1.

void swap(int *a, int *b) 
{ 
    int temp = *a; 
    *a = *b; 
    *b = temp; 
} 
void sort012(int a[], int arr_size) 
{ 
    int lo = 0; 
    int hi = arr_size - 1; 
    int mid = 0; 

    while (mid <= hi) 
    { 
        switch (a[mid]) 
        { 
        case 0: 
            swap(&a[lo++], &a[mid++]); 
            break; 
        case 1: 
            mid++; 
            break; 
        case 2: 
            swap(&a[mid], &a[hi--]); 
            break; 
        } 
    } 
}
#3

okay bhaiya, thank you.

#4

and bhaiya, As i’d just completed the binary search module, Now how to approach the question of binary search while i will do questions?

#5

@CODER_JATIN, logic is quite simple when it comes to binary search , if the question is about finding maximum and minimum and you can check if some value x can be answer , then you can use binary search in the range of value x can take ,
you must practice popular questions like
book allocation
painter’s partion
agressive cow
to get the jest of binary search, just keep practicing that’s all it needs

#6

ok bhaiya, I’m not able to understand book allocation too much from the video tutorial.
can you please help me?

#7

what part are you having trouble with

#8

Bhaiya , Now understood ,thank You.