검색 알고리즘 - 노마드 코더

<검색 알고리즘>
인풋이 많아지면 시간도 오래 걸려
Linear Time Complexity(선형 시간복잡도)라고 해.
더 발전된 방식 있어
이진검색 알고리즘(Binary Search)
모든 배열에 쓸 수는 없어
정렬된 배열(Sorted Array)에서만 사용 가능
어떤 알고리즘은 특정 자료구조에서만 사용 가능해
이진 검색 알고리즘이 바로 그 경우

선형 검색은 어느 배열에서도 가능하지만 이진 검색은 아냐
sorted array에서만 가능. 배열들이 순서대로 정렬된 경우에만 사용가능
그러나!! 이렇게 정렬된 배열에 아이템을 추가하는 것은 정렬이 안된 경우보다 시간이 더 걸려

그러나 또한 정렬된 배열에서 검색을 하는 것은 정말 겁나 빨라
정렬이 안된 경우보다 훨씬~~

정렬 안된 배열은 그냥 공간이 있으면 맨 끝에 추가만 하면 됨. 겁나 빨라 그냥 추가만 하면 됨.

정렬된 배열에 8을 추가하려면 해당 배열에서 8보다 큰 아이템을 일단 찾아야 함. 8을 해당 아이템의 왼쪽에 추가해야함
이작업을 위해서 인덱스 0부터 작업을 시작해야지

배열에 추가하고 정렬하는 것에 시간을 투자하면 
검색을 하는 순간에 넘나 보람을 느낄거야

이진 검색에서 '이진'은 말 그대로 Binary, '0'과'1'을 의미하지 않아
'반으로 쪼개는 것'을 뜻함
하나를 두개로 쪼개는 것을 뜻하지

선형검색과 달리 이진 검색에서는 인덱스 0부터 처음부터 검색을 하지 않아
이진 검색에서는 중간에서 시작 정렬의 정중앙에서 시작한다.
정가운데 있는 숫자가 우리 목표 숫자보다 큰지 작은지를 봄

이진검색은 거대한 배열을 다룰때 효율적이지만 이진검색을 하고 싶다면 배열을 정렬해야한다.시간이 소요
검색을 많이 하는 상황이라면 정렬을 해야한다는 것
하지만 배열 정렬을 하려면 아이템 추가시 시간이 소요된다는 것
이러한 상충관게를 명확히 인지해야한다. 따라서 알고리즘과 데이터구조를 알아야하는 것. 이렇게 서로 연결되어있으니까

 

 

https://www.youtube.com/watch?v=WjIlVlmmNqs&t=182s