이진검색

이진검색이란? 요소(데이터)가 정렬 된 배열일 때 선형검색보다 좀 더 빠르게 검색할 수 있는 알고리즘. 특징? 1. 검색단계를 한 단계 진행 시마다 검색범위가 대략 절반 가량 줄어든다. ( 시간 복잡도 : O(log n) ) -> 선형검색의 경우 첫 번째 요소부터 마지막 요소까지 순차적으로 검색해나가며 원하는 값을 찾아나가기에 정렬이 크게 필요하지는 않다. 그러나 이진검색의 경우 첫 번째 요소가 아닌 검색 범위의 중앙 요소를 기준으로 원하는 값의 대소여부를 파악하며 범위를 대략 절반씩 줄여나간다. 그렇기에 반드시 데이터가 정렬되어 있어야한다. 2. 검색 요소를 한칸 씩 이동하며 검색하는 것이 아닌 범위의 중앙 요소를 검색 대상으로 한다. -> 검색하는 요소의 위치가 여러 칸으로 이동한다. 코드? publ..

• format_list_bulleted 알고리즘&자료구조/검색 알고리즘
• · 2022. 9. 13.
• textsms

선형검색(순차검색)

선형검색(순차검색)이란? 요소가 직선형태로 나열된 배열에서 검색하고자 하는 값을 찾을 때까지 맨 앞 요소부터 순차적으로 검색하는 알고리즘 검색 종료 조건? ① 순차적으로 검색하는 중 원하는 값 찾기 성공! (n회 검색) -> 배열 안에 값이 동일한 요소들이 있더라도 가장 먼저 값을 찾으면 검색 종료! ② 마지막 요소까지 검색해도 찾지 못했을 경우 실패!(n+1회 검색) * 요소 하나씩을 검색할 때마다 위 종료조건 2개를 판단해야한다. (=조건판단에 의한 비용발생) 사용 조건? 요소(데이터)가 정렬되어 있지 않은 상태로 저장된 배열에서 원하는 요소(값)을 찾고자 할 때 사용할 수 있는 유일한 방법이다. 코드 ? public class SeqSearch { static int seqSearch(int[] a..

• format_list_bulleted 알고리즘&자료구조/검색 알고리즘
• · 2022. 9. 12.
• textsms