순서 표 찾기

* 8195 ° 8195 ° (Searching) 는 컴퓨터 에서 비교적 자주 사용 하 는 조작 으로 주어진 값 에 따라 검색 표 에서 키 워드 를 주어진 값 과 같은 기록 이나 요 소 를 확인 하 는 것 을 말한다.표 에 이러한 요소 가 존재 한다 면 검색 에 성공 했다 고 합 니 다. 그렇지 않 으 면 검색 에 실 패 했 음 을 표시 합 니 다.
    오늘 우리 가 말 하고 자 하 는 검색 은 순서 표를 바탕 으로 하 는 검색 을 말 하 며 주로 정적 검색 (Static Search) 을 말한다. 즉, 검색 과정 에서 메타 표 의 요소 수정 과 관련 되 지 않 는 다 는 것 이다.
1. 순서 찾기 (Sequential Search)
『 8195 』 순서 찾기 는 선형 찾기 라 고도 부 릅 니 다. 표 의 첫 번 째 요 소 를 시작 으로 주어진 키워드 와 점차적으로 비교 하 는 것 을 말 합 니 다. 순서 표 의 특정한 요소 가 주어진 키워드 와 같 으 면 검색 에 성공 한 것 을 의미 합 니 다. 그렇지 않 으 면 검색 에 실 패 했 음 을 나타 냅 니 다.코드 로 표시:

//        
let numberList = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92]

///              
///              
///  ，      Comparable  
extension Array where Element: Comparable {


    ///              
    /// -   key:     ，               
    /// - returns:      ，   true，    false
    func linearSearch(forElement key: Element) -> Bool {

        //     
        for number in self {

            if number == key {

                return true

            }
        }

        return false

    }

}


//        
let isNotFound: Bool = numberList.linearSearch(forElement: 8)  //    false
let isFound = numberList.linearSearch(forElement: 88)  //    true

즉, 순서 표 의 요소 가 많 을 수록 효율 이 떨어진다 는 것 이다.따라서 이것 은 표 에 있 는 요소 가 비교적 적은 순서 표 에 만 적합 하 다. 만약 표 에 있 는 요소 가 매우 많다 면 우 리 는 다른 방법 을 생각해 야 한다.
2. 반절 찾기 (Binary Search)
* 8195: 8195: 순서 표 에 있 는 요소 가 비교적 많 을 때 검색 효율 을 높이 기 위해 우 리 는 절반 으로 찾 을 수 있 습 니 다.절반 으로 나 누 어 찾 는 작업 원 리 는 순서 표 에서 첫 번 째 요소 의 색인 min 과 마지막 요소 의 색인 max 를 확정 한 다음 에 중간 요소 의 색인 mid 를 확정 하고 중간 요소 의 색인 mid 에 따라 중간 요 소 를 추출 한 다음 에 이 요소 로 주어진 관건 적 인 글자 와 비교 하 는 것 이다. 만약 에 중간 요소 가 주어진 키워드 보다 크 면이 는 우리 가 찾 아야 할 요소 범위 가 (min, mid - 1) 사이 에 있 음 을 나타 내 고 반절 찾기 를 계속 사용 해 야 한 다 는 것 을 의미한다.만약 에 중간 요소 가 주어진 키워드 보다 작다 면 우리 가 찾 아야 할 요소 의 범위 가 (mid + 1, max) 사이 에 있다 는 것 을 의미한다.중간 요소 가 주어진 키워드 와 같다 면 검색 에 성 공 했 음 을 나타 낸다.코드 로 표시:

//        
var numberList = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92]

extension Array where Element: Comparable {

    /// Array      。            ，              ，
    ///             mutating  
    mutating func binarySearch(forElement key: Element) -> Bool {

        var result = false

        //     
        let min = self.startIndex  //     
        let max = self.endIndex - 1  //     
        let mid = self.midIndex()  //     

        //     (        ，          )
        if key > self[max] || key < self[min] {

            //           
            print("  \(key)    ")

            return false
        }

        //          
        let n = self[mid]

        //              key
        if n > key {

            //              ，         
            //       min mid - 1      
            var slice = Array(self[...(mid - 1)])  //  Swift 3    ：var slice = Array(self[min...mid - 1])

            //      slice      
            result = slice.binarySearch(forElement: key) }

        //              key
        else if n < key {

            //              ，         
            //       mid + 1 max      
            var slice = Array(self[(mid + 1)...]) //  Swift 3    ：var slice = Array(self[mid + 1...max])

            //      slice      
            result = slice.binarySearch(forElement: key) }

        else {

            //          
            print("              \(key)")
            result = true
        }

        //        
        return result
    }

    ///        
    func midIndex() -> Index { return startIndex + (count / 2) }

}


//     
let isFound: Bool = numberList.binarySearch(forElement: 88)

『 8195 』 절 반 검색 의 효율 은 O (logn) 로 순서 검색 의 효율 보다 높 지만 절 반 검색 은 순서 저장 구조의 질서 표 에 만 적용 되 고 선형 링크 에 대해 서 는 절 반 검색 을 사용 할 수 없습니다.