Monthly Archives: June 2013

Finding the first occurence of a number in a sorted array.

Let us consider an array of numbers sorted in ascending order which can possibly contain duplicates. How do we find the left most/first occurrence of a given number?
The moment we read searching in a sorted array binary search should come to our mind. But Binary search has a limitation that it just finds out if a particular element exists in the array. If array contains duplicate entries, binary search finds out any matching index. But we want to find out the left most occurrence.

For example let us consider an array [1,2,2,3,4] and we have to find the element 2. The binary search finds out 2 at the index 2(assuming the array index starts with 0) and returns. But we actually have to return index 1 because it is the first occurrence.

One brute-force method is to find the occurrence of the element and keep moving left until we reach the first occurrence. But this approach is not effective. Let us consider an example to understand this.

If the input array contains just one element repeated n times. [1,1,1,1,1]. We want to find out the first occurrence of 1. First we find 1 at the index 2, then we have to traverse n/2 places backwards in this worst case. So the time complexity is O(n) which is as good as linear search.

Then how can we modify the binary search to solve this problem with O(log n) time complexity?

Modify the binary search algorithm such that if a matching entry is found, instead of returning, compare the middle element with the previous element. If they do not match, we found the first occurrence. Otherwise search the left half for the first occurrence. This approach guarantees to take O(log n) time to find that first occurrence. Below is the implementation of this approach in C++.

#include<iostream>

using namespace std;
//modified binary search method to find the first occurence
//of an element in the sorted array
int findFirst(int *array, int d, int l, int h)
{
while( l <= h)
{
int m = (l+h)/2;
//if element is found
if( array[m] == d )
{
//have we reached the beginning of the array
//or middle and it's previous elements are equal?
//search the left half
if( m > 0 && array[m] == array[m-1])
{
h= m-1;
}
else
return m; //we found the first occurence return it.
}
//following two conditions are similar to the binary search
else if ( array[m] < d)
{
l = m+1;
}
else
{
h = m-1;
}
}
return -1;
}

int main()
{
int n;
cin>>n;
int *array = new int[n];
int i;
for( i = 0 ; i < n ; i++)
cin>>array[i];
int x;
cin>>x;
cout<<x<<" found at "<<findFirst(array,x,0,n-1);
delete[] array;
return 0;
}

Program to shuffle an array

In some applications like card games, we need to shuffle an array of objects. In this post we will consider the problem of shuffling an array of numbers so that the same algorithm would be applicable for any type of arrays.

We use the random number generator in this algorithm. Let us consider an array of n numbers. It’s element are in the range of 0 to n-1 indices. We first select a random number between 0 to n-1 indices,and swap the random element with the last element. In the next iteration, we exclude the last element (thus reducing the array size by 1) and repeat the same procedure.

Here is the Java code which implements this approach.

import java.util.Random;

/**
*
* @author Ravi
*/
public class ShuffleArray {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int [] array = new int[10];
int i;
//fill the array with numbers 1-100
for( i = 0 ; i < 10 ; i++)
{
array[i] = i+1;
}
//call shuflle array method
shuffleArray(array);
//print the shuffled array
for( i = 0 ; i < 10 ; i++)
{
System.out.print(array[i]+" ");
}
}
public static void shuffleArray(int[] array)
{
int i;
//random number generator
Random rd = new Random();
//start from the end
for( i = array.length-1 ; i > 0 ; i--)
{
//generates a random number between [0,i] inclusive
int randomIndex = rd.nextInt(i+1);
//swap the element at random index with ith element
int temp = array[randomIndex];
array[randomIndex] = array[i];
array[i] = temp;
}
}

}

How does a selection sort works

Like Bubble sort, Selection sort is also a comparison based sorting algorithm, but it uses lesser number of swappings. Selection sort works this way. In first iteration it selects the smallest element and keep it in the first place. In the second iteration it selects the next smallest element from the remaining elements and keep it in the second place, and so on.

For example let the input array be [3,1,2,5,4]. Here are the snapshots of the array
in each iteration
[3,1,2,5,4] – smallest element – 1
[1,3,2,5,4] – next smallest element – 2
[1,2,3,5,4] – next smallest element – 3 – no swapping required as it is already in correct position.
[1,2,3,5,4] – next smallest element – 4
[1,2,3,4,5] – Done!

Unlike the bubble sort, selection sort has no mechanism to detect if an array is already sorted. Even if the array is sorted, all iterations are to be completed to fully sort the array.

The following C++ function implements the above technique.
 

void selection_sort(int *array, int n)
{
int i,j,smallInd;
//outer loop runs for n-1 iterations
for( i = 0 ; i < n-1 ; i++)
{
//assume array[i] is smallest
smallInd = i;
//search for smaller element from index i+1
for( j = i+1; j < n ; j++ )
{
//update if smaller element is found
if( array[j] < array[smallInd])
{
smallInd = j;
}
}
//place the smallest element in its correct position
if( i != smallInd) //dont swap the same elements
swap(array[i],array[smallInd]);
}
}

Explaining recursion with a simple example

In this post we will see a simple example which explains the concept of recursion.
Recursion is nothing but defining a problem in terms of itself. For example let us consider the problem of finding the sum of all the elements in an array. We can define the problem as follows.

Let sum(array,n) denotes the sum of the elements of an array of size n.
We can define sum(array,n) = sum(array,n-1) + array[n]

sum(array,n-1) is sum of the elements of array of size n-1 which actually is the same problem but with a smaller input size – the smaller sub-problem. If we write a function to solve the original problem, we can use the same function to solve this sub-problem also. There should be one base-case where we no longer need recursion to solve the smallest problem possible. In this case, the smallest sub-problem would be an array with just one element. What is the sum of elements in such an array? That single element itself. Then we work backwards to solve increasingly bigger sub-problem.
The following program illustrates the above concept.

#include <iostream>
using namespace std;
//This is a recursive function to find the sum of
//the elements in an array
int findSumRecursive(int *array,int n)
{
//Base cases
//if the array is empty return 0
if( n <= 0)
return 0;
//If the array has only one element, return that
//It is first as well as last element
else if( n == 1)
return array[n-1];
//recursive case
else
return array[n-1] + findSumRecursive(array,n-1);
}
int main()
{
int n;
cin>>n; //read array size
int i;
//dynamically allocate memory for the array
int *array = new int[n];
//read array elements
for( i = 0 ; i < n ; i++)
{
cin>>array[i];
}
cout<<findSumRecursive(array,n)<<endl;
//free the memory if it is no loner needed
delete[] array;
return 0;
}