Array search functions in PHP - Time & Space Complexity

Time Complexity: Array search functions

O(n)

Understanding Time Complexity

When we search for a value in an array, the time it takes depends on how many items are in the array.

We want to understand how the search time grows as the array gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function searchArray(array $arr, $target) {
    foreach ($arr as $item) {
        if ($item === $target) {
            return true;
        }
    }
    return false;
}

This code looks through each item in the array to find if the target value exists.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element in the array.
• How many times: Up to once for each item until the target is found or the array ends.

How Execution Grows With Input

As the array gets bigger, the search might check more items.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows roughly the same as the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to search grows linearly with the size of the array.

Common Mistake

[X] Wrong: "Searching an array always takes the same time no matter how big it is."

[OK] Correct: The search might have to check many items, so bigger arrays usually take longer.

Interview Connect

Understanding how search time grows helps you explain and improve code that works with lists.

Self-Check

"What if the array was sorted and we used a binary search instead? How would the time complexity change?"

Practice

1. Which PHP function returns the key of a value in an array if found, or false if not found?

easy

A. in_array

B. array_search

C. array_key_exists

D. array_keys

Solution

1. Step 1: Understand function purpose

   array_search looks for a value and returns its key if found.

2. Step 2: Compare with other functions

   in_array returns true/false, not key; array_key_exists checks keys; array_keys returns all keys.

3. Final Answer:

   array_search -> Option B

4. Quick Check:

   Key returned by array_search = array_search [OK]

Hint: array_search returns key, in_array returns true/false [OK]

Common Mistakes:

• Confusing array_search with in_array
• Thinking array_key_exists returns value
• Assuming array_keys searches values

2. Which of the following is the correct syntax to check if the value 5 exists in array $arr using in_array?

easy

A. in_array(5, $arr);

B. in_array($arr, 5);

C. in_array($arr => 5);

D. in_array(5 => $arr);

Solution

1. Step 1: Recall in_array syntax

   The correct syntax is in_array(value, array).

2. Step 2: Match syntax with options

   in_array(5, $arr); matches in_array(5, $arr); which is correct.

3. Final Answer:

   in_array(5, $arr); -> Option A

4. Quick Check:

   in_array(value, array) = in_array(5, $arr) [OK]

Hint: Remember in_array(value, array) order [OK]

Common Mistakes:

• Swapping parameters order
• Using arrow syntax instead of comma
• Passing array as first argument

3. What is the output of the following PHP code?

$arr = ['apple', 'banana', 'cherry'];
$key = array_search('banana', $arr);
echo $key;

medium

A. 0

B. banana

C. false

D. 1

Solution

1. Step 1: Understand array_search behavior

   It returns the key of the searched value if found.

2. Step 2: Check array keys and searched value

   Array keys are 0=>'apple', 1=>'banana', 2=>'cherry'. Searching 'banana' returns key 1.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   array_search('banana', $arr) = 1 [OK]

Hint: array_search returns index/key of found value [OK]

Common Mistakes:

• Expecting value instead of key
• Confusing false with 0
• Assuming it returns boolean

4. Identify the error in the following PHP code snippet:

$arr = ['x' => 10, 'y' => 20];
if (array_search(30, $arr)) {
    echo 'Found';
} else {
    echo 'Not Found';
}

medium

A. array_search returns false but condition treats 0 as false

B. array_search returns key but 30 is not in array, so condition fails correctly

C. array_search should be replaced with in_array for this check

D. No error, code works as expected

Solution

1. Step 1: Analyze array_search return and condition

   array_search returns key or false. If key is 0, condition fails because 0 is falsey.

2. Step 2: Check searched value presence

   30 is not in array, so array_search returns false, condition is false, prints 'Not Found'. But if value was at key 0, condition would fail incorrectly.

3. Step 3: Suggest correct function for boolean check

   Use in_array which returns true/false directly for presence check.

4. Final Answer:

   array_search should be replaced with in_array for this check -> Option C

5. Quick Check:

   Use in_array for boolean presence check [OK]

Hint: Use in_array for true/false presence checks [OK]

Common Mistakes:

• Using array_search in if without strict check
• Ignoring 0 key treated as false
• Not using === to check false

5. Given the array $data = ['a' => 0, 'b' => false, 'c' => null, 'd' => '0'];, which function call correctly checks if the value 0 exists in the array considering type?

hard

A. in_array(0, $data, true);

B. array_search(0, $data);

C. in_array(0, $data);

D. array_search('0', $data, true);

Solution

1. Step 1: Understand strict checking

   Using third parameter true enforces type checking in in_array and array_search.

2. Step 2: Analyze array values and types

   Values are 0 (int), false (bool), null, and '0' (string). Only strict check distinguishes 0 (int) from others.

3. Step 3: Choose correct function and parameters

   in_array(0, $data, true) returns true only if exact int 0 found. array_search without strict may confuse types.

4. Final Answer:

   in_array(0, $data, true); -> Option A

5. Quick Check:

   Use in_array with strict=true for exact type match [OK]

Hint: Use in_array with strict=true to check exact value and type [OK]

Common Mistakes:

• Ignoring strict parameter causing false positives
• Using array_search without strict for type-sensitive check
• Confusing '0' string with 0 integer