Binary Search in sorted and shifted (rotated) array

Binary Search in sorted and shifted (rotated) array

  Wednesday, August 10, 2016    1 comment

We know that Binary Search can be used to find an element in a sorted array of elements in O(log n) time. The algorithm is very versatile and with little modifications, it can be utilized in many more places for efficiency. Let us see one such problem.

Problem statement: You've been given an array that is sorted and then rotated by some unknown offset. For example, consider a sorted array arr[] = {1, 2, 3, 4, 5}. This array is now rotated, say twice, to the right such that arr[] = {4, 5, 1, 2, 3}. The offset of rotation is not known to you for a given array. Devise a way to find an element in the rotated array in O(log n) time.

Modified Binary Search approach: Now how efficiently can one search in this sorted + rotated array? The key is to find the offset position, i.e. the position at which array order is changed. For example, in the above array arr[], the offset position can be taken as index 1 (where element 5 is stored) because the very next element is the actual starting element of the sorted array, which is the smallest element. It can be seen that the array is divided into two sorted sub-arrays at the offset position.

So, if the offset is known to us, we can apply Binary Search in the two sorted sub-arrays one by one to find out the element in O(log n) time. Now all we have to worry about is finding the offset, and that too in O(log n) running time. This can be accomplished via a modified Binary Search, which considers the fact that the offset element is the only element in the array for which the very next element to it is smaller. By using this as a condition, we can find the offset.

Solution: Here is a C program which implements the above approach.

#include <stdio.h>

/* Function to find the offset position in O(log n) via modified Binary Search */
int findOffset(int *arr, int low, int high, int size)
{
    int mid;
    if (low <= high)
    {
        mid = low + ((high - low) / 2);

        if (arr[mid] > arr[mid+1])
            /* Offset position found at mid */
            return mid;
        else
        if (arr[mid] > arr[size-1])
            /* Offset may be on the right hand side, as arr[mid] is greater than the very last element in arr[] */
            return findOffset(arr, mid+1, high, size);
        else
            /* Offset may be on the left hand side */
            return findOffset(arr, low, mid-1, size);
    }

    return -1;    // No offset found in arr[]
}

/* Function for performing Binary Search to find item in the array */
int binarySearch(int *arr, int low, int high, int item)
{
    int mid;
    if (low <= high)
    {
        mid = low + ((high - low) / 2);

        if (arr[mid] == item)
            return mid;
        else
        if (arr[mid] > item)
            return binarySearch(arr, low, mid-1, item);
        else
            return binarySearch(arr, mid+1, high, item);
    }

    return -1;
}

/* Main function */
int main()
{
    int i, size, offset, item, index, *arr;
    printf("\nEnter size of array: \n");
    scanf("%d", &size);
    arr = (int*)malloc(size * sizeof(int));

    printf("\nEnter elements in array: \n");
    for (i = 0; i < size; i++)
        scanf("%d", &arr[i]);

    printf("\nEnter search item: \n");
    scanf("%d", &item);

    /* Get the position of offset (rotation) */
    offset = findOffset(arr, 0, size-1, size);

    /* If the array was not rotated, use normal Binary Search */
    if (offset == -1)
    {
        index = binarySearch(arr, 0, size-1, item);
        (index != -1) ? printf("Item found at index  %d.\n", index) : printf("Item not found.\n");
    }
    /* Otherwise the array was rotated, use Binary Search in left and right sub-arrays separately */
    else
    {
        /* Search in the sub-array till the offset position */
        index = binarySearch(arr, 0, offset, item);
        if (index != -1)
            printf("Item found at index  %d.\n", index);
        else
        {
            /* Search in the sub-array right of the offset position */
            index = binarySearch(arr, offset+1, size-1, item);
            (index != -1) ? printf("Item found at index  %d.\n", index) : printf("Item not found.\n");
        }
    }

    return 0;
}

Read More

There may be a bug hidden in your Binary Searches and Merge Sorts!

There may be a bug hidden in your Binary Searches and Merge Sorts!

  Wednesday, August 10, 2016    No comments

Your implementation of the Binary Search algorithm might be having a concealed bug in it! This Binary Search bug applies equally to Merge Sort and many other Divide and Conquer algorithms. If you have any code that implements one of these algorithms, better fix it now before it messes something up.

Here is a generally seen Binary Search code (in Java):

public static int binarySearch(int[] a, int item) {
    int low = 0;
    int high = a.length - 1;

    while(low <= high) {
        int mid = (low + high) / 2;

        if(a[mid] == item)
            return mid;        // Key found
        else if (a[mid] < key)
            low = mid + 1
        else
            high = mid - 1;
    }

    return -(low + 1);         // Key not found
}

The bug is in this line:

int mid = (low + high) / 2;    // Problem!

What the above line does is that it sets mid to the average of low and high, truncated down to the nearest integer. At a glance, nothing seems to be wrong in that, but it fails for large values of the int variables low and high. Specifically, it fails if the sum of low and high is greater than the maximum positive int value (2³¹ - 1). The sum overflows to a negative value and the value stays negative when divided by two, causing the array to go out of bounds. In Java, it throws ArrayIndexOutOfBoundsException while in C it causes unpredictable results. This bug can manifest itself for arrays whose length (in elements) is 2³⁰ or greater (roughly a billion elements).

So now we want to fix it, right? Here are some ideas to correct the line:

int mid = low + ((high - low) / 2);

Also note that right shifting a number by one bit is equivalent to dividing it by 2. We can utilize the unsigned right shift operator (>>>) available in Java. The >>> operator lets you treat int and long as 32-bit and 64-bit unsigned integral types (Java does not provide unsigned int and unsigned long data types).

int mid = (low + high) >>> 1;

In C and C++, where you don't have the >>> operator, you can do this:

int mid = ((unsigned int)low + (unsigned int)high)) >> 1;

Note:

• You should always check array algorithms for possible overflow.
• Elements that are meant to store array indexes should be taken as unsigned int.

(Credit to this article on Google Research Blog for the above concepts.)

Read More

Binary Search

Binary Search

  Tuesday, August 09, 2016    No comments

Binary search, also known logarithmic search or half-interval search, is a "Divide and Conquer" search algorithm that finds the position of a target value within a sorted array in run-time complexity of Ο(log n). It is one of the fundamental algorithms in Computer Science. For this algorithm to work properly the data collection should be in sorted form.

Binary search searches for a particular item by comparing it with the middle element of the array. If match occurs, then index of the middle element is returned. If the item is smaller than the middle element, then it is searched in the left sub-array of the middle element, otherwise the item is searched in the right sub-array of the middle element. This process continues on the sub-arrays as well, till the item is found or the size of sub-array reduces to zero.

(Image from Wikipedia)

Time Complexity: O(log n)
Space Complexity: O(1) in iterative implementation and O(log n) in recursive implementation (considering the recursion call stack space).

Both iterative and recursive implementations of Binary Search are shown here:

1. Iterative Binary Search:

int binarySearch(int *A, int size, int item)
{
    int start = 0, end = (size - 1), mid;

    while(start <= end)
    {
        mid = (start + end) / 2;

        if(A[mid] == item)
            return mid;            // Item found at index mid

        else if(A[mid] > item)
            end = mid - 1;         // Item may be on the left sub-array

        else
            start = mid + 1;       // Item may be on the right sub-array
    }

    return -1;    // Not found
}

2. Recursive Binary Search:

int binarySearch(int *A, int start, int end, int item)
{
    int mid;

    if(start <= end)
    {
        mid = (start + end) / 2;

        if(A[mid] == item)
            return mid;

        else if(A[mid] > item)
            return binarySearch(A, start, mid-1, item);

        else
            return binarySearch(A, mid+1, end, item);
    }

    return -1;
}

Note: The above Binary Search algorithms may fail in some cases. See this post for detail: There may be a bug hidden in your Binary Searches and Merge Sorts!

Read More

Randomized Quick Sort algorithm - O(n log n) worst case complexity

Randomized Quick Sort algorithm - O(n log n) worst case complexity

  Tuesday, August 09, 2016    No comments

The worst case time complexity of a typical implementation of Quick Sort is O(n²). The worst case occurs when the picked pivot is always an extreme (smallest or largest) element, which happens when the input array is either sorted or reversely sorted and either first or last element is picked as pivot.

Randomized Quick Sort algorithm (with random pivot):

In the randomized version of Quick sort we impose a distribution on input by picking the pivot element randomly. Randomized Quick Sort works well even when the array is sorted/reversely sorted and the complexity is more towards O(n log n). (Yet, there is still a possibility that the randomly picked element is always an extreme.)

Here, we will pick a random pivot position with the help of rand() function (defined in stdlib.h header file). Then we can swap pivot element with the element at the Left position (or the Right position in some implementations) and Quick Sort the array.

void swap(int *A, int x, int y) {
    int temp;
    temp = A[x];
    A[x] = A[y];
    A[y] = temp;
}

int getPivot(int Left, int Right) {
    return ( rand() % (Right - Left + 1) ) + Left;
}

void quickSort(int *A, int Left, int Right) {
    if(Left > Right)
        return;
    
    int i, pos, pivot;

    // Choosing pivot element randomly:

    pivot = getPivot(Left, Right);  // Get a random pivot
    swap(A, Left, pivot);           // Take A[pivot] to Left index and then do Quick Sort

    // Quick Sort the array:

    pos = Left;
        
    for(i = Left+1; i <= Right; i++)
        if(A[i] < A[Left])
            swap(A, ++pos, i);

    swap(A, Left, pos);  // By now, pos must be at proper position for A[Left].
                         // So we swap A[Left] with A[pos]

    quickSort(A, Left, pos-1);     // Sort left sub-list
    quickSort(A, pos+1, Right);    // Sort right sub-list
}

Read More

Quick Sort

Quick Sort

  Monday, August 08, 2016    2 comments

Quick Sort is a Divide and Conquer sorting algorithm. It picks an element as pivot element and partitions the given array around the picked pivot such that pivot element comes at its proper sorted position and the elements smaller than pivot element are on its left hand side and the elements larger than pivot element are on its right hand side. Now it recursively sorts the left sub-array and right sub-array of pivot element in the same manner till no further partitioning can be done.

There are many different versions of Quick Sort that pick pivot in different ways, like:

1. Always pick first element as pivot. (implemented below)
2. Always pick last element as pivot.
3. Pick a random element as pivot.
4. Pick median as pivot.

The key process in Quick Sort is partitioning. The target of partitions is that given an array and an element x of array as pivot, put x at its correct position (as that in sorted array) and put all elements smaller than x before x and all elements greater than x after x in the array. All this should be done in linear time.

Time complexity: O(n log n) in average case, O(n²) in worst case (Here worst case is when array is sorted or reversely sorted.)
Space complexity: O(log n) in average case, up to O(n) in worst case (This extra space may come from the call stack.)

Although the worst case time complexity of Quick Sort is O(n²) which is more than many other sorting algorithms like Merge Sort and Heap Sort, Quick Sort is faster in practice because its inner loop can be efficiently implemented on most architectures, and in most real-world data. The algorithm can be modified to make it much more efficient. For example, Randomized Quick Sort shows O(n log n) complexity even for worst case, as it picks pivot randomly.

Quick Sort can be implemented in different ways by changing the choice of pivot, so that the worst case rarely occurs for a given type of data. However, Merge Sort is generally considered better when data is huge and stored in external storage.

Below is one of the many ways to implement Quick Sort:

#include <stdio.h>

void swap(int *x, int *y)
{
    int temp = *x;
    *x       = *y;
    *y       = temp;
}

void quickSort(int *A, int Left, int Right)
{
    int i, pos;
    if(Left < Right)
    {
        pos = Left;
        for(i = Left+1; i <= Right; i++)
            if(A[i] < A[Left])
                swap(&A[++pos], &A[i]);   // When order is mismatched, increment pos and swap A[pos] with A[i]

        swap(&A[Left], &A[pos]);   // By now, pos is at proper position for A[Left]. Actually Left acts as pivot element here! Now swap A[Left] with A[pos]

        quickSort(A, Left, pos-1);     // Sort left sub-list
        quickSort(A, pos+1, Right);    // Sort right sub-list
    }
}

int main()
{
    int i, size;
    printf("\n\nEnter size of array: ");
    scanf("%d", &size);
    int A[size];

    printf("\n\nEnter %d elements: \n", size);
    for(i = 0; i < size; i++)
        scanf("%d", &A[i]);
 
    quickSort(A, 0, size-1);

    printf("\n\nQuick sorted: ");
    for(i = 0; i < size; i++)
        printf("%d ", A[i]);
 
    return 0;
}

Read More

Merge Sort

Merge Sort

  Monday, August 08, 2016    1 comment

Merge sort is a "Divide and Conquer" algorithm which divides input array into two halves, calls itself for the two halves and then merges the two sorted halves. Basically, merge sort merges two sorted sub-arrays into one sorted array. For example: Let array A[] = {4, 5, 8, 9} and array B[] = {1, 2, 6, 10}, then the resulting array C[] = {1, 2, 4, 5, 6, 8, 9, 10}.

Merge sort is shown below for merging two separate sorted arrays into one sorted array, and then for merge-sorting a given unsorted array with help of recursion.

1. Merging two sorted arrays into one sorted array:
The idea is to place index variables i and j at start of the two arrays A[] and B[] respectively. Now compare the corresponding elements of the two arrays, copy the smaller element into the result array C[] and increment that index. Also, when one of the arrays is completely exhausted, just copy the remaining elements from the other array into the result.

void mergeSort(int *A, int *B, int *C, int sizeA, int sizeB, int sizeC)
{
    int a = 0, b = 0, c = 0;
    
    while(c < sizeC)
    {   
        if(a >= sizeA)          C[c++] = B[b++];    // Array A[] was exhausted
        else if(b >= sizeB)     C[c++] = A[a++];    // Array B[] was exhausted
        else if(A[a] < B[b])    C[c++] = A[a++];
        else                    C[c++] = B[b++];
    }
}

2. Merge sort a given array with help of recursion:
Now we know that we need two sorted arrays and we can merge sort them. Given an unsorted array, we can keep on splitting the array into two halved (sub-arrays) until size of sub-arrays reaches one. Now we can merge sort the sub arrays back to the actual array of given size, but in sorted order. The function mergeSortRecursive() is used to part the array into sub-arrays recursively until single elements are reached. The merge() function is used for merging two halves. This function merge(A, left, mid, right) assumes that sub-arrays A[left..mid] and A[mid+1..right] are sorted and merges the two sorted sub-arrays into one.

Time complexity: O(n log n)
Space complexity: O(n) (For taking an auxiliary array.)

#include <stdio.h>

void merge(int *A, int left, int mid, int right)    // For merge-sorting the array partitions A[left to mid] and A[mid+1 to right]
{
    int B[right];
    int i = left, j = mid+1, k;

    for(k = left; k <= right; k++)
    {
        if(i > mid)               B[k] = A[j++];    // Left array was exhausted. Copy right sub-array directly
        else if(j > right)        B[k] = A[i++];    // Right array was exhausted. Copy left sub-array directly
        else if(A[i] < A[j])      B[k] = A[i++];
        else                      B[k] = A[j++];
    }

    for(k = left; k <= right; k++)
        A[k] = B[k];
}

void mergeSortRecursive(int *A, int left, int right)    // For partitioning array recursively [in O(log n)] and then merge-sorting the 2 parts [in O(n)] via merge() function
{
    int mid;

    if(left < right)
    {
        mid = (left + right) / 2;
        mergeSortRecursive(A, left, mid);       // Partition
        mergeSortRecursive(A, mid+1, right);    // Partition

        merge(A, left, mid, right);             // Merge sort
    }
}

int main()
{
    int i, size;
    printf("\n\nEnter size of array: ");
    scanf("%d", &size);
    int A[size];

    printf("\n\nEnter %d elements: \n", size);
    for(i = 0; i < size; i++)
        scanf("%d", &A[i]);

    mergeSortRecursive(A, 0, size-1);

    printf("\n\nMerge sorted: ");
    for(i = 0; i < size; i++)
        printf(" %d ", A[i]);

    return 0;
}

Here is a diagram that tries to explain what is happening in recursive merge sort (taken from Wikipedia):

Read More