Hashing Approach
Hashing is an approach that employs a hash function to map elements in an array to locations, within a data structure, usually known as a hash table. When you have an urgent need to locate a number this method proves to be highly effective.
Steps to solve the problem:
- Start by setting up a hash table and create a hash function that maps values to indices, in the table.
- Take each element from the array. Insert it into the hash table using the hash function.
- When you want to find a number apply the hash function to that target value then locate its corresponding index in the hash table and finally check if the target value is stored there.
- This method allows for retrieval of numbers when needed.
Implementation of the above approach:
// C++ code for the above approach:
#include <iostream>
#include <unordered_map>
using namespace std;
int findNumber(int arr[], int n, int target)
{
unordered_map<int, int> hT;
for (int i = 0; i < n; i++) {
hT[arr[i]] = i;
}
if (hT.find(target) != hT.end()) {
return hT[target];
}
else {
return -1;
}
}
// Drivers code
int main()
{
int arr[] = { 10, 20, 30, 40, 50 };
int n = sizeof(arr) / sizeof(arr[0]);
int target = 30;
int index = findNumber(arr, n, target);
// Function Call
if (index != -1) {
cout << "Target found at index " << index << endl;
}
else {
cout << "Target not found in the array." << endl;
}
return 0;
}
import java.util.HashMap;
public class Main {
static int findNumber(int[] arr, int n, int target) {
HashMap<Integer, Integer> hT = new HashMap<>();
for (int i = 0; i < n; i++) {
hT.put(arr[i], i);
}
if (hT.containsKey(target)) {
return hT.get(target);
} else {
return -1;
}
}
public static void main(String[] args) {
int[] arr = { 10, 20, 30, 40, 50 };
int n = arr.length;
int target = 30;
int index = findNumber(arr, n, target);
// Function Call
if (index != -1) {
System.out.println("Target found at index " + index);
} else {
System.out.println("Target not found in the array.");
}
}
}
using System;
using System.Collections.Generic;
class Program {
static int FindNumber(int[] arr, int target)
{
Dictionary<int, int> hashTable
= new Dictionary<int, int>();
for (int i = 0; i < arr.Length; i++) {
hashTable[arr[i]] = i;
}
if (hashTable.ContainsKey(target)) {
return hashTable[target];
}
else {
return -1;
}
}
static void Main(string[] args)
{
int[] arr = { 10, 20, 30, 40, 50 };
int target = 30;
int index = FindNumber(arr, target);
// Function Call
if (index != -1) {
Console.WriteLine("Target found at index "
+ index);
}
else {
Console.WriteLine(
"Target not found in the array.");
}
}
}
// Function to find the index of a target number in an array
function findNumber(arr, target) {
// Create a new Map to store the array elements and their indices
let elementMap = new Map();
// Populate the Map with array elements and their indices
for (let i = 0; i < arr.length; i++) {
elementMap.set(arr[i], i);
}
// Check if the target number is present in the Map
if (elementMap.has(target)) {
// Return the index of the target number
return elementMap.get(target);
} else {
// Return -1 if the target number is not found in the array
return -1;
}
}
// Driver code
function main() {
// Example array
const arr = [10, 20, 30, 40, 50];
// Target number to be searched
const target = 30;
// Call the findNumber function to get the index of the target number
const index = findNumber(arr, target);
// Display the result based on the index value
if (index !== -1) {
console.log("Target found at index", index);
} else {
console.log("Target not found in the array.");
}
}
// Run the main function
main();
def find_number(arr, target):
hash_table = {}
for i, num in enumerate(arr):
hash_table[num] = i
if target in hash_table:
return hash_table[target]
else:
return -1
# Driver code
if __name__ == "__main__":
arr = [10, 20, 30, 40, 50]
target = 30
index = find_number(arr, target)
# Function Call
if index != -1:
print(f"Target found at index {index}")
else:
print("Target not found in the array.")
Output
Target found at index 2
Time complexity: O(1), but in worst case scenarios it can degrade to linear (O(n)). Hashing usually provides O(1) time complexity, for retrieving data. However there are instances when hash collisions occur.
Auxiliary space: The space complexity is linear (O(n)) because you need to store all elements within the hash table.
Find the Target number in an Array
Finding a number within an array is an operation, in the field of computer science and data analysis. In this article, we will discuss the steps involved and analyze their time and space complexities.
Examples:
Input: Array: {10, 20, 30, 40, 50} , Target: 30
Output: “Target found at index 2”Input: Array: {10, 20, 30, 40, 50}, Target: 40
Output: “Target found at index 3”