Leetcode: Median of Two Sorted Arrays in C++

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Either Drop the right side of Bigger one or left side of the small one. 
Solution:
int findMid(int A[], int m,  int B[], int n, int k)
{
        if(m<=0) return B[k-1];
        if(n<=0) return A[k-1];
        if(k<=1)
        return min(A[0], B[0]);
        if(A[m/2]>B[n/2])
        {
            if(m/2+n/2+1<k)
                 return findMid(A, m, B+n/2+1, n - n/2-1, k-n/2-1 );
            else
                return findMid(A, m/2, B, n, k);
        }
        else
        {
            if(m/2+n/2+1<k)
                return findMid(A+m/2+1, m- m/2-1, B, n, k-m/2-1 );
            else
                return findMid(A, m, B, n/2, k);
        }
    }
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if((m+n)%2==0)
        return (findMid(A,m,B,n,(m+n)/2)+findMid(A,m,B,n,(m+n)/2+1))/2.0;
        else
        return findMid(A,m,B,n,(m+n)/2+1);
    }

Leetcode: Search for a Range in C++

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,

Given [5, 7, 7, 8, 8, 10] and target value 8,return [3, 4].


Solution:
vector<int> searchRange(int A[], int n, int target) {
        vector<int> result(2, -1);
        int start =0;
        int end =n-1;
        int mid =0;
        while(start<=end)
        {
            mid = start+(end-start)/2;
            if(A[mid]==target)
            {
                int left = mid;
                int right = mid;
                while(left>=0&&A[left]==target) left--;
                while(right<n&&A[right]==target) right++;
                left++;
                right--;
                result[0] = left;
                result[1] = right;
                return result;
            }
            else if(A[mid]>target)
                end = mid-1;
            else
                start = mid+1;
        }
        return result;
    }

Leetcode: Search a 2D Matrix in C++

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.

• The first integer of each row is greater than the last integer of the previous row.

[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]

For example,

Consider the following matrix:

Given target = 3, return true.

Solution:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
         if(matrix.size()==0)
         return false;
         int row = matrix.size();
         int column = matrix[0].size();
         int start = 0;
         int end = row-1;
         int mid = 0;
         while(start<=end)
         {
            mid = start+(end-start)/2;
            if(matrix[mid][0]>target)
            {
                end = mid-1;
            }
            else if(matrix[mid][0]<target)
            {
                start = mid+1;
            }
            else
                return true;
         }
         if(end<0)
         return false;
         int cur = end;
         start = 0;
         end = column-1;
         while(start<=end)
         {
            mid = start+(end-start)/2;
            if(matrix[cur][mid]>target)
            {
                end = mid-1;
            }
            else if(matrix[cur][mid]<target)
            {
                start = mid+1;
            }
            else
                return true;
         }
         return false;
    }

Leetcode: Search Insert Position in C++

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0


Solution:
int searchInsert(int A[], int n, int target) {
        int start = 0;
        int end = n-1;
        int mid = 0;
        while(start<=end)
        {
            mid = start+(end-start)/2;
            if(A[mid]>target)
            {
                end = mid-1;
            }
            else if(A[mid]<target)
            {
                start = mid+1;
            }
            else
                return mid;
        }
        return start;
    }

Leetcode: Search in Rotated Sorted Array II in C++

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

bool search(int A[], int n, int target) {
        int start = 0;
        int end = n-1;
        while(start<=end)
        {
            int mid = start+(end-start)/2;
            if(A[mid]==target)
             return true;
            if(A[mid]>A[start])
            {
                if(target>=A[start]&&target<A[mid])
                end = mid-1;
                else 
                start = mid+1;
            }
            else if(A[mid]<A[start])
            {
                if(target>A[mid]&&target<=A[end])
                start = mid + 1;
                else
                end = mid -1;
            }
            else
                start++;
        }
        return false;
    }

Leetcode: Sqrt in C++

Implement int sqrt(int x).
Compute and return the square root of x.
Solution:
int sqrt(int x) {
        int start  = 0;
        int end = x;
        double cur = x;
        while(start<=end)
        {
            double mid = start + (end-start)/2;
            double result = mid*mid;
            if(result == cur)
            return mid;
            else if(result>cur)
            end = mid-1;
            else
            start = mid+1;
        }
        return end;
    }

Leetcode: Divide Two Integers in C++

Divide two integers without using multiplication, division and mod operator.Solution: O(log(a/b))
unsigned int unsigndivide(unsigned int dividend, unsigned int divisor, unsigned int& mod)
    {
        if(divisor == dividend)
        {
            mod = 0;
            return 1;
        }
        else if(divisor>dividend)
        {
            mod = dividend;
            return 0;
        }
        else
        {
            unsigned int addup = divisor+divisor;
            if(dividend>=addup)
            {
                unsigned int result1 = unsigndivide(dividend, addup, mod);
                unsigned int result2 = unsigndivide(mod, divisor, mod);
                return result1+result1+result2;
            }
            else
            {
                mod = dividend - divisor;
                return 1;
            }
        }
    }
    int divide(int dividend, int divisor) {
        bool flag = false;
        if((dividend>0&&divisor<0)||(dividend<0&&divisor>0))
          flag = true;
        unsigned int abs_dividend=abs(dividend);
        unsigned int abs_divisor =abs(divisor);
        unsigned int mod =0;
        unsigned int result = unsigndivide(abs_dividend, abs_divisor, mod);
        if(flag)
        return 0-result;
        return result;
    }

Leetcode: Search in Rotated Sorted Array in Java

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

Solution:
 public int help(int[] A, int target,int start, int end)
    {
        if(start>end)
        {
            return -1;
        }
        int mid = (start+end)/2;
        if(A[mid] == target)
        return mid;
        else if((A[mid]>A[end]&&target>A[end]&&target<A[mid])||(A[mid]<A[end]&&(target<A[mid]||target>A[end])))
        return help(A,target, start, mid-1);
        else
        return help(A,target, mid+1, end);
    }
    public int search(int[] A, int target) {
        if(A.length==0)
        return -1;
        return help(A,target, 0, A.length-1);
    }