The Algorithm Design Manual Chapter 4 Problem 34

Suppose that you are given a sorted sequence of distinct integers {a1 , a2 , . . . , an },
drawn from 1 to m where n < m. Give an O(lg n) algorithm to find an integer ≤ m that is not present in a. For full credit, find the smallest such integer.

package avdongre.tadm;

public class SmallestMissingNumber {
	public int findSmallestMissingNumber(int[] arr) {

		int low = 0;
		int high = arr.length - 1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (arr[mid] > mid + 1) {
				high = mid - 1;
			} else if (arr[mid] <= mid + 1) {
				low = mid + 1;
			}
		}
		return low + 1;
	}

	public static void main(String[] args) {
		SmallestMissingNumber smn = new SmallestMissingNumber();
		{
			int[] arr = new int[] { 1, 2, 4, 5 };
			System.out.println(smn.findSmallestMissingNumber(arr));
		}

	}

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s