## 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 array
```

#### Example

__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 array
```

#### Example

__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.