[자료구조] 선형 검색과 이진 검색
선형 검색 인덱스를 하나씩 증가시켜 확인하는 방법. 배열의 사이즈가 n이면 찾는 값이 제일 첫 번째 값이면 1단계만에 끝낼 수 있지만 마지막에 존재하면 n단계나 필요함. 정렬이 안 되도 사용가능 이진 검색 배열의 중간값의 인덱스의 값보다 큰 지 작은 지 확인. 크면 작은 값을, 작으면 큰 값을 전부 배제해 나아가며 진행. 예시) [1, 2, 3, 4, 5, 6, 7, 8] 에서 1를 원한다고 가정. 1. 중간 인덱스 4보다 1이 작기 때문에 [1,2,3]에 존재함을 판단. 2. 중간 인덱스 2보다 1이 작기 때문에 [1]에 존재함을 판단. 3. 중간 인덱스 1이 1과 같기 때문에 인덱스를 반환. 배열의 사이즈가 n일 때 2^k보다 작거나 같으면 최대 k단계만에 판별이 가능하다. 예시) 위 예시의 배열 사..
