인덱스2 [알고리즘] 이분 탐색(Binary Search) 1. 이분 탐색 - 정렬된 배열에서 찾고자 하는 수를 찾는 방법 - 계속해서 두가지 경우로 나누면서 탐색 - 인덱스를 이용해 탐색 - 시간복잡도 : O(logN) 2. 탐색 방법 1. 배열의 첫번째 인덱스와 마지막 인덱스 번호를 각각 left, right로 저장 2. left와 right의 중간지점인 mid의 인덱스를 (left+right)/2 를 이용해 구함 3. left가 right보다 커지는 시점까지 반복 -> left보다 right가 커지면 찾고자 하는 수가 없는 경우임 4. 배열의 mid번째 값과 내가 찾고자 하는 값을 비교 4-1. 내가 찾고자 하는 값이 mid보다 작은 경우 - 최소한 mid - 1번째 인덱스의 값보다는 작거나 같기 때문에 right를 mid-1로 변경시켜 최대값을 바꿔줌(구.. 2023. 10. 18. [면접 준비] 배열이 순차적으로 데이터를 저장하는 이유 1. 배열의 특징 - 데이터를 순차적으로 저장 - 인덱스를 이용하여 데이터에 빠르게 접근 가능 2. 배열이 순차적으로 저장되는 이유 - 실제 메모리 상에서 데이터가 순차적으로 저장되면 맨 앞의 주소와 해당 자료형의 byte수, 인덱스 번호만으로 데이터에 접근할 수 있기 때문이다.([2,4,5] -> 2의 주소 1000 -> 5의 주소 = 2의 주소(1000) + int형(4byte)*인덱스번호(2) = 1008) - 즉, 인덱스를 이용해 데이터에 빠르게 접근하기 위해 순차적으로 저장되는 것이다. 3. 데이터가 순차적으로 저장되는 배열의 단점 - 삽입 삭제가 느림 -> 삭제나 삽입 시 해당 위치 이후의 모든 원소들을 한칸씩 이동시켜야하기 때문 - resizing이 어려움 -> 크기가 예측이 어려운 데이터를.. 2023. 7. 26. 이전 1 다음