순차 검색

---

💡관련 자료구조: 배열

---

검색

저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
목적하는 탐색 키를 가진 항목을 찾는 것

검색의 종류

순차검색
이진검색
인덱싱 (DB와 밀접)

순차 검색

일렬로 되어 있는 자료를 순서대로 검색하는 방법
앞에서부터 끝까지 전부 검색
정렬이 되어 있든 되어 있지 않든 시간복잡도는 동일
1. 정렬되어 있지 않은 경우
2. 정렬되어 있는 경우

정렬되어 있지 않은 경우

첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하면 찾는다.
키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환한다.
자료구조의 마지막에 이를 때까지 검색 대상을 찾지 못하면 검색 실패

public class Search {
	static int[] nums = { 8, 123, 18, 321, 45, 418, 324, 64 };

	public static void main(String[] args) {
		System.out.println(searchForNoSort(45));
		System.out.println(searchWhileNoSort(45));
	}// main


	// 찾았다. 못찾았다 가 필요하면 boolean
	// 찾았으면 어디에서 찾았는지가 중요하면 int
	static boolean searchForNoSort(int key) {
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] == key)
				return true;
		}
		return false;
	}


	// while문으로도 작성을 해보자.
	static boolean searchWhileNoSort(int key) {
		int idx = 0;
		while (idx < nums.length) {
			if (nums[idx++] == key) {
				return true;
			}
		}
		return false;
	}
 }

정렬되어 있는 경우

자료가 오름차순으로 정렬된 상태에서 검색을 실시한다고 가정하자.
자료를 순차적으로 검색하면서 키 값을 비교하여, 원소의 키 값이 검색 대상의 키 값보다 크면 찾는 원소가 없다는 것이므로 더 이상 검색하지 않고 검색을 종료한다. 즉, 정렬되어 있지 않은 경우와 다르게 중간에 검색을 중단할 수 있다.
👉반복문에서 System.out.println(i); 찍어서 검사해보기

public class Search {
	static int[] nums = {2, 4, 7, 9, 11, 19, 23};
	static int len = nums.length;
	
	public static void main(String[] args) {
		
		System.out.println(searchForSort(23));
		System.out.println(searchWhileSort(10));
		
	}// main

	
	static int searchForSort(int key) {
		for(int i=0; i < len; i++) {
			if(key == nums[i]) {
				return i;
			}
		}
		return -1;
	}
	
	
	static int searchWhileSort(int key) {
		int i=0;
		while(i<len && key >= nums[i]) {
			if(key == nums[i]) {
				return i;
			}
			i++;
		}
		return -1;
	}
	
} //end class