Runtime of searching for a number in an array?

Searching for a number in an array is said to have a runtime of O(n) because there may be cases where the number doesn't exist in the array. In such cases, you'd have to have gone through the entire array, which is O(n).

But how about in the case where we know the number definately exists in the array? Does the runtime change then?

Also is there a way to find out the average number of searches it would have to do before a number is found in an array based on its size?

Regardless of whether the number is present in the array, all n elements will still be examined in the worse case. For example if searching for the number 5:

array1 = {6, 8, 3, 7, 8, 2}
array2 = {6, 8, 4, 9, 4, 5}

Searching array1 will require looping over all 6 elements (leading to 5 not being found).
Searching array2 will also require examining all 6 elements, with the final element being 5 and the search returning true.

As for the average number of searches, I believe you are referring to the average number of elements examined? This is difficult. If you are wondering what the average case is for arrays of ints with length 6, you would need to generate all possible permutations of arrays of ints with length 6, then search them all for your desired number (say 5) and calculate the average. This will differ again if you only include permutations that have at least one element which is 5 (average will improve).

For a brute force search algorithm like this, all you can really be certain of is that the average case will be somewhere between the best best case O(1) (5 is first element of the array) and the worst O(n)

StackExchange Computer Science Q#13244, answer score: 3