October 30, 2020
읽기
O(1) 소요
→ 인덱스의 메모리 주소가 1068인 배열이 있다면 인덱스 3에 접근 할 때는 1068+3인 1071 메모리 주소로 바로 가면 된다.
검색
정렬된 배열일 경우 O(log n) 소요
Function binary_search(array, value)
lower_bound = 0
upper_bound = array.length - 1
while lower_bound <= upper_bound do
midpoint = (upper_bound + lower_bound) / 2 and round off midpoint
value_at_mid = array[midpoint]
if value < value_at_mid
upper_bound = midpoint - 1
else if value > value_at_mid
lower_bound = midpoint + 1
else if value is same with value_at_mid
return midpoint
// 상한선과 하한선이 같아졌는데도 value랑 value_at_mid가 일치하지 않았다면
// array 안에 value가 없다는 의미
return null
정렬되지 않은 배열일 경우 O(n) 소요
삽입
삭제
💡 정렬된 배열: 삽입은 다소 느리지만(O(n)) 검색은 훨씬 빠르다(O(log n)).
💡 정렬되지 않은 배열: 삽입은 빠르지만(O(1)) 검색이 훨씬 느리다(O(n)).
복제
int[] a = {1, 2, 3, 4, 5};
int[] b = a.clone();
출력
System.out.print("a =");
for (int i = 0; i < a.length; i++)
System.out.print(" " + a[i]);
Source
A Common-Sense Guide to Data Structures and Algorithms