Searching
탐색에는 크게 두가지 알고리즘이 존재함
-
Linear or Sequential Algorithm
-> 하나하나 순차적으로 탐색을 수행함->Implement
using System;
namespace Reb{
class Program{
public static void Main(string[] args){
int[] searchList = new int[]{1,2,3,65,75,34,4,8};
int result, n;
n = Console.ReadLine();
result = LinearSearch(searchList, n);
if(result == -1)
Console.WriteLine($"Target value {n} is can't find in List.")
else
Console.WriteLine($"Target value {n} is in {result} index of List.")
}
public static int LinearSearch(int[] arr, int key){
int length = arr.Length;
for(int i =0; i<length ; i++){
if(arr[i].Equals(key)){
return i;
}
}
return -1;
}
}
}- Binary Algorithm or Interval Search
-> 정렬되어있는 데이터들사이에서 절반씩 나누면서 탐색을 수행하기에 훨씬 효율적이다.
-> Implement //use reculsive
using System;
namespace Reb{
Class Program{
static void Main(stirng[] args){
int[] searchList = new int[]{3,4,6,7,8,9,21,25,1313};
BinarySearch(searchList, 0, 8, 7);
}
static int BinarySearch(int[] arr, int start, int end, int key){
int length = arr.Length;
if(r>=1){
int mid = (end -start+1)/2;
if(key == arr[mid]){
return mid;
}
else if(key > arr[mid]){
ruturn BinarySearch(arr, ,start mid-1,key);
}
else
return BinarySearch(arr, mid+1, end, key);
}
return -1;
}
}
DFS(Depth-First-Search)
시작은 bfs와 동일하게 root나 임의의 node에서 시작하며, 한노드에서 갈수있는 최대한 먼 범위의 branch까지 탐색한 후에 backtracking기법으로 돌아오면서 순회
BFS(Breadth-Fir st-Search)
tree나 graph형태의 자료구조에서 사용되는 searching algorithm이다
시작은 tree의 root나 임의의 node에서 시작하며, 다음 계층의 노드를 확인하기 전까지 인접한 노드를 먼저 살핀다.
BFS는 시작점에서부터 목표점까지 최단거리를 찾는데 많이 사용된다.
대신 DFS보다 일반적으로 많은 메모리를 소모한다.
Implement
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Graph{
private int _V;
Lin
}
cf) Searching의 종류 컴퓨터 관련
1. Internal Searching
메인메모리나 주요한 메모리에서 데이터를 탐색해봄
2. External Searching
외장메모리나 Secondary Memory에서의 데이터를 탐색
cf)Secondary memory is computer memory that is non-volatile, persistent and not immediately accessible by a computer or processor. It allows users to store data and information that can be retrieved, transmitted, and used by apps and services quickly and easily.
참조)
더 편하게 더 간단하게