Binary Search

Question 1

Pseudo code for searching pivot index in sorted rotated array?

Answer 1

private int FindPivotIndex(int[] nums)
        {
            int low = 0;
            int pivotIndex = 0;
            int high = nums.Length - 1;
            //array is sorted already 
            if (nums[low] < nums[high])
                return 0;

            while (low < high)
            {
                pivotIndex = low + ((high - low) / 2);
                //! pivot element is one having left element  and right element  less than it.
                //! Comparing only on the right side is enough
                if (nums[pivotIndex] > nums[pivotIndex + 1])
                {
                    return pivotIndex;
                }
                // !Pivot element always present in the non uniformly increasing part
                //! if first element is less than pivot index element than it means its strictly increasing 
                //! we need to search on  right side as its non uniformly increasing part
                else if (nums[low] < nums[pivotIndex])
                {

                    low = pivotIndex + 1;
                }
                else
                {
                    //! why pivotIndex and why not pivotIndex-1? 
                    //!because element at pivot index can also be the part of the non uniformly increasing 
                    high = pivotIndex;
                }
            }
            return pivotIndex;

    }

Question 2

Implement int sqrt(int x).

Answer 2

public int MySqrt(int x) {
if (x < 2) return x;
int l = 2;
int r = x / 2;

        while (l <= r)
        {
            int mid = l + ((r - l) / 2);
            long num = (long)mid * mid;

                if (num > x)
                {
                    r = mid - 1;
                }
                else if (num < x)
                {
                    l = mid + 1;
                }
                else
                {
                    return mid;
                }
            }
            return r;  
    }

Question 3

What is the inflection point in sorted/rotated array?

Answer 3

https://medium.com/spotthedifference/search-in-a-rotated-sorted-array-72c12bcb212
The point which divides the array into two parts can be seen as a point of change, hence let’s call this point as inflection point.

Question 4

what is the pivot element in an array?

Answer 4

http://theoryofprogramming.com/2017/12/16/find-pivot-element-sorted-rotated-array/
The pivot element is basically, the largest element in an array. For a sorted and rotated array, it might be somewhere in between

Question 5

Given sorted array .How to find out how many times array has been rotated ?

Answer 5

http://theoryofprogramming.com/2017/12/16/find-pivot-element-sorted-rotated-array/
The number of times the array is rotated would be (IndexOfPivotReturned + 1).