# 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 arrayint 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 arrayint 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;}`