First Occurrence of a Value in an Array

Unity Engine
1

I have a built-in array of integers and I would like to find the first occurrence of a given value in that array, without having to iterate through it.

Is there a .Net/Mono collection command that will provide this? And if so, what’s the syntax for that?

Thanks a bunch in advance!

2

I’ve never heard of any Structure that would allow you to pull the first occurrence of a user specified value without any movement through the list/array, Unless that value was always the same and you organized the structure to always be the first value pop up.

Other then that as you populated array and kept that value that you were looking for and marked that location in a variable.

I am however limited by my current knowledge. I’m sure there are much more knowledgeable programmers that may offer further advice.

*Any way you could possibly post what your task your trying to complete?

3

Thanks, Eiznek.

Actually, I think that “Array.BinarySearch(array, value)” from Mono’s System library will do it, but I can’t get it to work right.

I’m using System.Array.BinarySearch(myArray, mySoughtIntgerValue); but I’m not getting the index in the array that I would expect.

4

Got it!

It’s not “BinarySearch” I need to use, it’s that beloved workhorse “IndexOf”.

Here’s a working example for anyone else who might ever need it:

var item : int = System.Array.IndexOf(myArray, mySoughtIntegerValue);

Enjoy!

5 
            int[] array = { 1, 2, 3 };

            Console.WriteLine(Array.BinarySearch(array, 2));

            Console.ReadLine();

Ignore this - go with IndexOf().

6

Binary Search still iterates through your list. It probably even sorts it before hand as well. Since BST(Binary Search Tree) is a structure like a Reversed Tree it organizes your data in a way that it will travel to either the left or the right of the root value…

ex -

                                          [50] 

                                     [25]       [75]

                               [5]    [35]    [65]   [100]
7

Sorry, Eiznek, I should have been clearer.

When I said “without iterating”, I meant something along the lines of “without my having to iterate in code”.

I want to use the Mono library because I assume that letting it iterate for me will generally be faster than doing it with a longhand-coded loop.

It does seem to be a bunch faster too.

8

Yeah no problem. I just misunderstood what you meant. Yeah BST’s are Logarithmic O( n log(n) ) speed while Simple sorting ( when you use two loops and such) are most often O(n^2)… Much more efficient.

Anyways good to know how to use the sort without writing your own like I always have had to do in college. Nice to see other Oregonian’s on here.

9

Array.BinarySearch assumes the array is already sorted - http://msdn.microsoft.com/en-us/library/system.array.binarysearch.aspx

You can call Array.Sort separately - the MSDN doc says that uses Quicksort - O(n log n) on average but O (n^2) worst case.

You’re right, it’s good to know the underlying algorithms. I had a phone interview with Google years ago, where they asked this exact question - how would you find a specific integer value in a sorted array? They were obviously asking for me to describe binary search (although my real life answer would be I probably wouldn’t bother and would call the most convenient built-in function).