📌선형 검색 알고리즘

• 가장 자연스러운 검색 방법
• 맨 처음 배열부터 검색을 시작해서 데이터를 찾는다.
• 최악의 시나리오 = 데이터가 가장 마지막 에 있는 것
  ⭐배열의 길이가 길어지는 만큼 검색 시간이 길어진다.
  
  

🔎선형 검색 과정

1. 처음부터 데이터(k=1)를 찾을 때까지 검색

2. 데이터를 찾으면 해당 인덱스(3) 반환

📈그래프 y = x

📌이진 검색 알고리즘

• 배열의 크기가 클 때 선형 검색보다 훨씬 좋은 알고리즘
• [1, 2, 3, 4, 5] 또는 [5, 4, 3, 2, 1] 과 같이 정렬이 끝난 배열에서 수행 가능
• 중앙값을 기준으로 왼쪽 또는 오른쪽 제외
• 단계마다 배열의 절반을 제외할 수 있기 때문에 속도가 빠르다.

🔎이진 검색 과정

x = 4
1. 왼쪽 끝(low)과 오른쪽 끝(high)의 인덱스 값으로 중앙값을 찾는다.

arr [ ( low + high ) / 2 ] = mid

arr[(0+6)/2] = arr[3] = 6

2. 데이터가 중앙값보다 크면 왼쪽을 제외하고 중앙값도가 작으면 오른쪽을 제외한다.

x = 4 < mid = 6

3. 남아있는 데이터에서 다시 중앙값을 찾는다.

x > mid → low = mid + 1
x < mid → high = mid - 1

4. low와 high가 같아질 때까지 위의 과정을 반복한다.

5. x = 4를 찾는다.

📈그래프 y=log x