Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Efficient algorithm to find first available name

I have an array containing names of items. I want to give the user the option to create items without specifying their name, so my program will have to supply a unique default name, like "Item 1".

The challenge is that the name has to be unique so i have to check all the array for that default name, and if there is an item with the same name i have to change the name to be "Item 2" and so on until i find an available name.

The obvious solution will be something like that:

String name = "Item ";
for (int i = 0; !isAvailable(name + i) ; i++);

My problem with that algorithm is that it runs at O(N^2).

I wonder if there is a known (or new) more efficient algorithm to solve this case.

In other words my question is this: Is there any algorithm that finds the first greater-than-zero number that dose NOT exist in a given array, and runs at less that N^2?

like image 448
Avi Shukron Avatar asked Jan 14 '11 21:01

Avi Shukron


People also ask

Is binary search faster than linear search?

Binary search is faster than linear search except for small arrays. However, the array must be sorted first to be able to apply binary search. There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search.

What is the best searching algorithm for unsorted array?

Binary Search. Sequential search is the best that we can do when trying to find a value in an unsorted array.

Which technique of searching an element in an array would you prefer to use and in which situation?

Binary Search is used for searching an element in a sorted array. It is a fast search algorithm with run-time complexity of O(log n). Binary search works on the principle of divide and conquer. This searching technique looks for a particular element by comparing the middle most element of the collection.


2 Answers

You can certainly do it in O(N) time, N being the number of items in your array:

  • One of "Item 1", "Item 2", ... "Item N+1" must be free, so create an array of N+1 flags.
  • Traverse the items, and for each name if it is of form "Item k" with 0 < k <= N+1, set that flag.
  • Scan the flag array for the first clear flag.

Additional memory requirement is N+1 bits, which certainly beats any data structure that actually stores all N names.

like image 64
Steve Jessop Avatar answered Oct 01 '22 07:10

Steve Jessop


Yes, there is.

First sort the array. Then run through it and return the first element whose value is not equal to its index (plus 1). The sort is O(n log n), the final step is O(n), so the entire thing is O(n log n).

If you put all items into a hash table, you can do it in O(n) at the cost of some space and an additional O(1) step at creation of new items. Since each element needs to be visited, O(n) is clearly optimal.

I'd be interested to see if there's an O(n) way to do this, without using any "persistent" data structure like the hash table. (And assuming unbounded integers, otherwise a bucket sort could be used as an O(n) sorting algorithm).

like image 35
Thomas Avatar answered Oct 01 '22 07:10

Thomas