Algorithm : Write a method that takes a sorted array A of integers and a key k and returns the index of first occurrence of k in A. Return -1 if k does does not appear in A.

Blog on Algorithms, Data Structures, Codes, Java and Mobile platforms
Sharing the bit I know
HomeAbout
« Implement a fast integer square root function that takes in a 32-bit unsigned integer and returns another 32-bit unsigned integer that is the floor of the square root of the input.Suppose that in addition to being sorted, the entries of A are distinct integers. Design an efficient algorithm for finding an index i such that A[i] = i or indicating that no such index exist »
Write a method that takes a sorted array A of integers and a key k and returns the index of first occurrence of k in A. Return -1 if k does does not appear in A.

public class FindFirstOccurrenceBinarySearch {

/**

• @param args

*/

public static void main(String[] args) {

int [] input = {1,1,1,1,2,2,2,3,3,3,3,3,3,3,4,4,4};

int key = 2;

System.out.println(“The first ocurrence of key :”+key +” is at:”+getFirstOccurrence(input,key));

}

private static int getFirstOccurrence(int[] input, int key) {

int low = 0;

int high = input.length-1;

int mid = 0;

int indexFound = -1;

while (low <= high)

{

mid = low + (high – low)/2;

if(key == input[mid])

{

indexFound = mid;

break;

}

else if(key > input[mid])

{

low = mid + 1;

}

else

{

high = mid -1;

}

}

if (indexFound != -1)

{

System.out.println(indexFound);

//first ocurrence must be between start of array and indexFound

low = 0;

high = indexFound;

while( low <= high)

{

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

System.out.println(low +”:”+high+”:”+mid);

if(key != input [mid])

{

low = mid + 1;

}

else

{

indexFound = mid;

high = mid – 1;

}

}

}

return indexFound;

}

}