Searching in Data Structures: An Overview
What is searching in data structures?
Types of searching in data structures
- Linear search: This is a simple searching algorithms in data structure that checks each element of the data structure until the desired element is found.
- Binary search: This algorithm is used for searching in a sorted array or list. It works by repeatedly dividing the search interval in half until the desired element is found or the search interval is empty.
- Hashing: Hashing is a technique that uses a hash function to map keys to their corresponding values. This makes it possible to quickly retrieve values based on their keys.
- Depth-first search (DFS): This is a search algorithm that is used for searching graphs or trees. It works by traversing the graph or tree in a depth-first manner, exploring as far as possible along each branch before backtracking.
- Breadth-first search (BFS): This is another search algorithm used for searching graphs or trees. It works by traversing the graph or tree in a breadth-first manner, exploring all the neighbors of a node before moving on to the next level.
Searching Techniques: Linear Search and Binary Search
Linear Search
- Start at the beginning of the list.
- Compare the target value with the current element in the list.
- If the current element matches the target value, the search is successful, and the position or index of the element is returned.
- If the current element does not match the target value, move to the next element in the list.
- Repeat steps 2-4 until a match is found or the end of the list is reached.
- If the end of the list is reached without finding a match, the search is unsuccessful, and a special value (e.g., -1) may be returned to indicate the absence of the target value
Pseudocode for Linear Search Algorithm
LinearSearch(array, target):
for each element in array, from left to right:
if element equals target:
return index of element
return -1 // target not found in the arrayExample
Python
num = int(input("Enter the number of elements in array: "))
arr = []
print("Enter", num, "integer(s):")
for cnt in range(num):
arr.append(int(input()))
search = int(input("Enter the number to search: "))
found = False
for cnt in range(num):
if arr[cnt] == search:
print(search, "is present at location", cnt+1, ".")
found = True
break
if not found:
print(search, "is not present in array.")
Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of elements in array: ");
int num = scanner.nextInt();
int[] arr = new int[num];
System.out.println("Enter " + num + " integer(s):");
for (int i = 0; i < num; i++) {
arr[i] = scanner.nextInt();
}
System.out.print("Enter the number to search: ");
int search = scanner.nextInt();
boolean found = false;
for (int i = 0; i < num; i++) {
if (arr[i] == search) {
System.out.println(search + " is present at location " + (i + 1) + ".");
found = true;
break;
}
}
if (!found) {
System.out.println(search + " is not present in array.");
}
scanner.close();
}
}
C++
#include <iostream>
using namespace std;
int main() {
cout << "Enter the number of elements in array: ";
int num;
cin >> num;
int arr[num];
cout << "Enter " << num << " integer(s):" << endl;
for (int i = 0; i < num; i++) {
cin >> arr[i];
}
cout << "Enter the number to search: ";
int search;
cin >> search;
bool found = false;
for (int i = 0; i < num; i++) {
if (arr[i] == search) {
cout << search << " is present at location " << (i + 1) << "." << endl;
found = true;
break;
}
}
if (!found) {
cout << search << " is not present in array." << endl;
}
return 0;
}
Explanation
In this example, the user can input an array's length and elements before being asked to enter a number to perform a search within the array. In a linear search, it determines whether the target number is present in the array and prints the location if it is; if not, it shows that the number is absent from the array.
Output
Enter the number of elements in the array:
5
Enter 5 integer(s):
10
20
30
40
50
Enter the number to search:
30
30 is present at location 3.Binary Search
- Start with a sorted array or list. For binary search to work correctly, the elements must be in ascending or descending order.
- Set two pointers, low and high, to the beginning and end of the search space, respectively. Initially, low = 0 and high = length of the array - 1.
- Calculate the middle index using the formula: mid = (low + high) / 2. This will give you the index of the element in the middle of the current search space.
- Compare the target value with the element at the middle index:
- If they are equal, the target value has been found. Return the index of the middle element.
- If the target value is less than the middle element, set high = mid - 1 and go to step 3.
- If the target value is greater than the middle element, set low = mid + 1 and go to step 3.
- Repeat steps 3-4 until the target value is found or low > high. If low becomes greater than high, it means the target value is not present in the array.
Pseudocode for Binary Search Algorithm
BinarySearch(array, target): left = 0 // Initialize the left pointer
right = Length(array) - 1 // Initialize the right pointer while left <= right:
mid = (left + right) / 2 // Calculate the middle index if array[mid] == target:
return mid // Target found at the middle index
else if array[mid] < target:
left = mid + 1 // Adjust left pointer
else:
right = mid - 1 // Adjust right pointer return -1 // Target not found in the arrayExample
Python
size = int(input("Enter the size of the list: "))
list = []
print("Enter", size, "integer values:")
for i in range(size):
element = int(input())
list.append(element)
sElement = int(input("Enter value to be searched: "))
f = 0
l = size - 1
m = (f + l) // 2
while f <= l:
if list[m] < sElement:
f = m + 1
elif list[m] == sElement:
print("Element found at index", m, ".")
break
else:
l = m - 1
m = (f + l) // 2
if f > l:
print("Element not found in the list.")
Java
import java.util.Scanner;
public class BinarySearch {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the size of the list: ");
int size = scanner.nextInt();
int[] list = new int[size];
System.out.println("Enter " + size + " integer values:");
for (int i = 0; i < size; i++) {
list[i] = scanner.nextInt();
}
System.out.print("Enter value to be searched: ");
int sElement = scanner.nextInt();
int f = 0;
int l = size - 1;
int m = (f + l) / 2;
while (f <= l) {
if (list[m] < sElement) {
f = m + 1;
} else if (list[m] == sElement) {
System.out.println("Element found at index " + m + ".");
break;
} else {
l = m - 1;
}
m = (f + l) / 2;
}
if (f > l) {
System.out.println("Element not found in the list.");
}
scanner.close();
}
}
C++
#include <iostream>
using namespace std;
int main() {
int size;
cout << "Enter the size of the list: ";
cin >> size;
int list[size];
cout << "Enter " << size << " integer values:" << endl;
for (int i = 0; i < size; i++) {
cin >> list[i];
}
int sElement;
cout << "Enter value to be searched: ";
cin >> sElement;
int f = 0;
int l = size - 1;
int m = (f + l) / 2;
while (f <= l) {
if (list[m] < sElement) {
f = m + 1;
} else if (list[m] == sElement) {
cout << "Element found at index " << m << "." << endl;
break;
} else {
l = m - 1;
}
m = (f + l) / 2;
}
if (f > l) {
cout << "Element not found in the list." << endl;
}
return 0;
}
Explanation
This example lets the user enter a list of integers and then ask for a particular value to utilize binary search to find inside the list. If the value is discovered, the index where it was found is printed; if not, it shows that the element is missing from the list.
Output
Enter the size of the list: 4
Enter 4 integer values:
1 3 5 7
Enter value to be searched: 10
Element not found in the list.FAQs
1. What is searching with example?
Finding a certain item or piece inside a database of information is the process of searching. A good example would be looking up a word in a dictionary.
2. What are the applications of searching?
Spell-checking, locating items in sorted lists, and other uses for searching include database queries, information retrieval in search engines, and more.
3. What is linear and binary search?
Binary search includes dividing a sorted list into two halves and removing one half based on comparison with the target element, whereas linear search involves scanning through each element one at a time to discover a target element.
4. What are the 2 types of searching algorithms in data structure?
Sequential search (also known as linear search) and binary search are the two types of search algorithms.
5. What are the 4 types of searching?
The term "four types of searching" typically refers to various algorithms or approaches, such as tree-based search, binary search, hash-based search, and linear search, each of which is appropriate for a particular situation and data structure.
Summary
Take our free skill tests to evaluate your skill!
In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.
Previous Tutorial
