이진탐색

---

시간복잡도

• 최선 : O(1)
• 평균 : O(N logN)
• 최악 : O(N logN)

---

과정

• 배열 -> [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]

1. 배열 내에 찾고자 하는 값을 정한다 -> 7을 찾는다라고 가정

2. 탐색할 배열의 위치를 지정한다
   -> left(왼쪽) : 0번 인덱스부터 탐색으로 지정
   -> right(오른쪽) : 마지막 인덱스까지 탐색으로 지정

3. 오른쪽과 왼쪽 인덱스의 중간지점을 찾는다
   -> mid(가운데)

4. 원하는 값이 mid(가운데)보다 상대적으로 앞에 있는지 뒤에 있는지 확인
   -> 앞에있는 경우 -> right = (mid - 1)
   -> 뒤에있는 경우 -> left = (mid + 1)
   -> 가운데에 있는 경우 -> 가운데에 값이 있으므로 해당 인덱스를 반환

5. right이나 left이 변경된 경우에는 mid의 값도 다시 갱신해야함

---

주의사항

• 이진탐색(Binary Search)는 가운데를 기준으로 값의 크기를 비교한 후 탐색하는 방식이기 때문에 탐색하고자 하는 배열이 정렬된 상태여야 한다

---

코드

// 탐색의 결과로 해당 값이 위치한 인덱스를 표시한다

func binaraySearch(_ arr: [Int], _ value: Int ) -> Int{
    // 탐색을 시작하는 첫 인덱스를 0으로 설정
    // 만약 탐색을 시작하는 인덱스가 1이상인 경우 원하는 숫자로 변경
    var left = 0
    var right = arr.count - 1
    
    while left <= right {
        let mid = left + (right - left)/2
        
        if value == arr[mid] {
            return mid
        }else if value > arr[mid] {
            left = mid + 1
        }else {
            right = mid - 1
        }
    }
    return -1
}