이진탐색

읽기, 검색, 쓰기, 삭제

배열[]을 사용할 때 생각해야할 요소다.

배열은 RAM에 저장되므로 읽기가 매우 빠르다.
크기를 처음에 정하며, 첫 주소와 인덱스를 통해 바로 해당 값을 읽는다.

검색은 다소 느리다.
배열을 처음부터 순회하는 선형검색을 생각하면
평균적으로는 찾는 값이 중간에 있을 것이고,
최선의 경우는 맨 처음.
최악의 경우는 맨 마지막에 있거나, 아예 없는 경우이다.

쓰기를 생각하면
먼저 배열의 크기를 생각해야 한다.

여유 공간이 있다면
평균적으로는 중간에 데이터가 insert 될 것이고, 넣는 위치의 이후 모든 값들은 오른쪽으로 한 칸씩 밀려나게 될 것이다.
최선의 경우는 맨 마지막에 넣는 경우이며, 바로 insert 가능하다.
최악의 경우는 맨 처음에 넣는 경우이다. 모든 값들이 오른쪽으로 한 칸씩 밀려나고, 맨 처음에 데이터가 insert 된다.

여유 공간이 없다면
배열 크기를 확장하여 새로 만들고, 기존 배열을 복사한 뒤, 위의 과정을 반복할 것이다.

삭제도 쓰기와 비슷하다.
평균적으로는 중간 데이터가 delete가 될 것이고, 삭제된 위치의 이후 값들은 모두 왼쪽으로 당겨질 것이다.
최선의 경우는 맨 마지막을 지우는 경우이며, 바로 delete 가능하다.
최악의 경우는 맨 처음을 지우는 경우이다. 맨 처음 데이터가 지워지고, 이후 모든 값들이 왼쪽으로 당겨진다.

==========================================================

검색 알고리즘에 대해 알아보자.

선형검색 이외에 이진검색이 있다.
이진검색은 정렬된 배열에만 사용가능하다.
O(logn)의 시간복잡도를 갖는다.

데이터의 길이가 2^n배가 되더라도, 검색 시간이 n배가 되는 것이 아니라, n번 더 확인하기만 한다.

 

ref.

https://www.youtube.com/watch?v=NFETSCJON2M 

https://youtu.be/WjIlVlmmNqs