[AL&DS] 선형검색, 이진검색

1. 선형검색 (좌 -> 우 하나씩 탐색)

// 선형검색 : O(N)
func linearSearch(_ary []int, _find int) bool {
	result := false
	for i := 0; i < len(_ary); i++ {
		fmt.Println("STEP : ", i+1)
		if _ary[i] == _find {
			result = true
			break
		}
	}
	return result
}

 

2. 이진검색 (MidPoint로 쪼개어 탐색)

// 이진검색 : O(logN)
func binarySearch(_ary []int, _find int) (bool, int) {
	lower := 0
	upper := len(_ary) - 1
	result := false
	resultIdx := 0

	for i := 0; i < len(_ary); i++ {
		if lower <= upper {
			result = false
		}

		midpoint := (upper + lower) / 2
		value_at_mid := _ary[midpoint]

		switch {
		case _find == value_at_mid:
			result = true
			resultIdx = midpoint
			return result, resultIdx
		case _find < value_at_mid:
			upper = midpoint - 1
		case _find > value_at_mid:
			lower = midpoint + 1
		}
	}
	return result, resultIdx
}

 

3. 비교

→ 선형검색 장점 : 정렬된리스트가 아니어도 사용 가능

→ 선형검색 단점 : O(N)의 시간복잡도를 가지며 원소수가 늘어나는만큼 단계수가 증가함

→ 이진검색 장점 : O(logN)의 시간복잡도를 가지며 선형검색보다 단계수가 적어 속도가 빠름

→ 이진검색 단점 : 정렬된리스트가 아니면 사용 불가능