Friday, November 9, 2012

First occurrence of a number in a sorted array


Given a sorted array of numbers where each number is repeated multiple times,  design an algorithm to find the first occurrence of a given number.
for e.g.
input array: {2,2,2,3,4,5,5,5,6,6,6,7,7,7,7,12,12,15,19}
number: 6
Here number 6 is found in position 8,9 and 10 (0-indexed). However, 8 is the first index.

Approach:- Using binary search locate the block of numbers containing the list of target number.
Once the list is found, apply binary search on the block again.

Solution

No comments:

Post a Comment

UA-36403895-1