검색

검색

@24.03.20

검색 알고리즘

💡

다양한 데이터 구조 내에서 원하는 데이터를 찾기 위한 과정

키

💡

찾고자 하는 값으로, 데이터 집합 내의 각 항목은 키와 연결된 값을 가지며,
이 키를 사용하여 해당 항목을 식별하고 검색할 수 있다.

• ex) 키 : 단어 → 키를 통해 단어의 정의를 찾는다.

배열의 검색

• 배열에서 데이터를 검색하는 방법에는 순차 검색과 이진검색이 존재

순차 검색

💡

배열의 첫 번째 요소부터 시작하여, 차례대로 각 요소를 키값과 비교하며, 검색하는 방법

• 구현은 간단하나, 대규모 데이터 집합에서는 비효율적이다. ⇒ 노가다 작업

• 예시

  boolean result = false;
  
  for(int i 0; i<array.length; i++){
  	if(key == array[i]){
  		System.out.println("찾았다!");
  		result=true;
  		}
  	}

이진 검색

💡

정렬되어 있는 배열에서 중간 지점의 값을 키와 비교하여 검색 범위를 반으로 줄이면서 검색하는 방법

• 보통 오름차순으로 정렬되어있다고 생각하고 검색

• 예시

  int low = 0; // 첫 인덱스
  int high = array.length-1; // 마지막 인덱스
  int mid = 0; //중간인덱스 
  
  while(low <=high){
  	mid = (low + high) / 2;
  	if(key == array[mid]){
  			return array[mid]; //return: 현재 실행 중인 메소드를 즉시 종료하고 그 값을 반환
  	}
  	else if(key > array[mid]){
  		low = mid + 1; 	 
  	}
  	else { 
  		high = mid -1;
  	}
  }