What the condition means actually?-CodePudding

Would anyone kindly explain how the condition inside this if else statement is working?

if ((mid == 0 || arr[mid - 1] <= arr[mid]) &&
    (mid == n - 1 || arr[mid   1] <= arr[mid]))
    return mid;

The above code is a part of the binary search algorithm. Below is the full code -

function findPeakUtil(arr, low, high, n)
{
let l = low;
let r = high - 1;
let mid;
 
while(l <= r)
{
 
    // finding the mid index by right shifting
       mid = (l   r) >> 1;
        
    // first case if mid is the answer
    if((mid == 0 || arr[mid - 1] <= arr[mid]) &&
    (mid == n - 1 || arr[mid   1] <= arr[mid]))
        break;

    // change the right pointer to mid-1
    if(mid > 0 && arr[mid - 1] > arr[mid])
        r = mid - 1;
           
    // change the left pointer to mid 1
    else
           l = mid   1;
   }
    
   return mid;

}

CodePudding user response：

Please next time add more detail about the code and question because this code isn't a binary search is from a question that asks for peak element in array -> https://www.geeksforgeeks.org/find-a-peak-in-a-given-array/

and what are you asking is what is the base case of that recursive idea. the base case is when the middle pointer is not smaller (aka equal or bigger) than its neighbors which is when arr[mid - 1] <= arr[mid] AND arr[mid 1] <= arr[mid]

Ther other conditions (arr[mid] = 0 / n-1) take care of when the mid is on of the corner elements.

but to understand why you always have a peak you should look on how high and low are peaked:

// If middle element is not peak and its
// left neighbour is greater than it,
// then left half must have a peak element
else if (mid > 0 && arr[mid - 1] > arr[mid])
    return findPeakUtil(arr, low, (mid - 1), n);

// If middle element is not peak and its
// right neighbour is greater than it,
// then right half must have a peak element
else
    return findPeakUtil(
        arr, (mid   1), high, n);

This make sure that there's always a peak element in the sub-array

CodePudding user response：

The condition should be clear when simplified to

arr[mid - 1] <= arr[mid] && arr[mid] >= arr[mid   1]

But when mid is one of the extreme positions in the array (0 or n-1), there are two issues:

the expression cannot be evaluated,
you need to give the expression an appropriate meaning anyway.

This is worked around by "guarding" the comparisons with tests on the value of mid. I leave it to you as an exercise to evaluate the condition in these two special cases, by substituting mid with 0 or n-1.