Search

Binary Search

The array should be sorted. The basic principle of this algorithm is to compare the key with the middle element. If key is equal to the middle element, the algorithm terminates returing the index. If key is greater than the middle element, search in the upper half otherwise search in the lower half. In every iteration we reduce the number of the elements by half(reduce the search space by half).

int search(vector<int>& nums, int key)
{
    int l = 0, u = nums.size() - 1;
    while(l <= u){
        int mid = ((u - l) / 2) + l;
        int midElement = nums[mid];
        if(midElement == key){
            return mid;
        }
        
        if(l == u){
            return -1;
        }
        
        if(midElement < key){
            l = mid + 1;
        }
        else{
            u = mid - 1;
        }
    }
    
    return -1;
}

Time Complexity: O(log n)

Kth Order Statistic

The main purpose of this algorithm is to find the Kth largest element in an array of elements. The main part of this algorithm is the partition function. Partition function takes an array and places an element in the final position. Final position refers to the position of that particular element in the sorted order.

For example: 7, 6, 8, 6, 6, 9, 78

If we take element as the key, then partition function will return: 7, 6, 6, 6, 8, 9, 78

As we can see clearly in the above example all the elements before 8 (7, 6, 6, 6) are smaller or equal to 8. And all the elements after 8 (9, 78) are greater than 8. All the elements in the lower part or upper part, considering key, are not sorted.

To find the Kth element we can run the partition function using any random key. If the index of the key is greater than K then the desired element lies in the lower part and vice versa.

Time Complexity: O(N)

int partition(vector<int>& arr, int left, int right){
    int l = left - 1;
    int x = arr[right];
    for(int i = left; i < right; i ++){
        if(arr[i] < x){
            l ++;
            swap(arr[l], arr[i]);
        }
    }
    
    l++;
    swap(arr[l], arr[right]);
    
    return l;
}

int findKthLargest(vector<int>& nums, int k){
    int length = nums.size();
    k = length - k;

    int l = 0;
    int u = length - 1;

    int partitionIndex = partition(nums, 0, length - 1);

    while(partitionIndex != k){
        if(k < partitionIndex){
            u = partitionIndex - 1;
        }
        else{
            l = partitionIndex + 1;
        }

        partitionIndex = partition(nums, l, u);
    }

    return nums[k];
}