Binary Search [이진검색 알고리즘]

Binary Search 이진검색 알고리즘

• 이진 이란? 반으로 쪼개는 것을 말한다. 하나를 2개로
• Sorted Array 정렬된 배열에서만 사용이 가능하다.
  이진검색은 선형검색과 다르게 인덱스0 부터, 처음부터 검색을 하지 않는다.

1. 정 가운데 있는 숫자가 우리 목표 숫자보다 큰지 작은지를 본다.
2. 만약 목표보다 큰 경우엔 아이템의 왼쪽으로 이동한다.
3. 만약 목표보다 작은 경우엔 아이템의 오른쪽으로 이동한다.
4. 그래서 10개의 아이템에서 3번만에 찾을수 있다.
5. 20개의 아이템에서 4번만에 찾을수 있다.

선형검색인 경우 10개의 아이템은 9번 , 19번 만에 찾을수 있었을 것이다.

이진검색은 거대한 배열을 다룰때 효율적이다.
그러나 이진검색을 하고싶다면 배열을 정렬해야한다.
(정렬을 하는것은 시간이 소요되는 일이다.)

Linear Search 선형검색 알고리즘

선형검색 알고리즘이란?
10개의 숫자가 있는 배열이 존재하는데 그 배열에서 7이라는 숫자를 찾는다면
1번 아이템부터 차례대로 7이 맞는지 확인하는것을 말한다.

• 선형검색 알고리즘의 최악은 맨 마지막에 아이템이 들어있거나?
• 배열안에 찾는 아이템이 존재하지 않거나!