이진 검색 - 더미용

반응형

그것은 무엇일까요?

당신이 J라는 글자를 찾기 위해 전화번호부를 찾고 있다고 가정해보세요. J를 한 페이지씩 확인하는 것 보다 중간에 책을 펼쳐서 검색을 시작하는 것이 훨씬 더 효과적일 것입니다. 그 책을 가운데로 펼쳐보면, 어떤 글자를 펼쳤는지 알게 될 거야. 그 글자가 J였나요? J를 찾았군요 만약 그 편지가 J보다 먼저 온다면, 당신은 J가 후반부에 있기 때문에 전화번호부의 반을 무시할 수 있다는 것을 알 것입니다. 만약 그 편지가 J 다음에 온다면, 당신은 J가 전반부에 있기 때문에 전화번호부의 나머지 반을 무시해도 된다는 것을 알 것입니다.

이진 검색은 기본적으로 J가 발견될 때까지 또는 전화 번호부에 선택 취소된 부분이 없을 때까지 ^를 반복하고 반복합니다.

시각적 예제

아래 도표에서, 우리는 0에서 10까지의 11개의 인덱스 길이를 가진 정렬된 배열을 볼 수 있다. 우리는 25번 번호를 찾고 있습니다. 첫 번째 반복에서는 전체 어레이를 고려한다는 것을 알 수 있습니다. 이것이 녹색 마커가 우리의 검색 섹션의 시작 부분인 색인 0과 검색 섹션의 끝 부분인 색인 10에 있는 이유입니다. 우리가 확인할 첫 번째 지수는 그 부분 중간에 있는 색인 색인 5입니다. 그 지수의 숫자는 14입니다. 이 배열은 정렬된 배열이고 14가 25보다 작기 때문에 숫자 25(있는 경우)는 색인 5 뒤에 있을 것입니다.

 

이 점을 알고 있으면 전체 어레이를 고려하는 대신 Index 6에서 Index 10까지의 나머지 어레이만 고려하도록 시작 마커와 끝 마커를 조정할 수 있습니다. 자, 다시 한 번 우리는 그 구역의 중간을 찾습니다. 그 구역의 중간은 24를 저장하는 색인 8입니다. 24가 25보다 작기 때문에, 우리는 이제 색인 8 이후의 섹션을 확인해야 한다는 것을 알고 있습니다. 즉, 새로운 검색 섹션은 색인 9에서 색인 10까지입니다. 만약 우리가 그 구역의 중간을 찾아서 반올림한다면, 우리의 새로운 "중간"은 색인 9로, 우리가 찾고 있는 숫자: 25를 저장합니다.

암호로 번역해줘요!

꼭 해야 한다면.

반복

 

두 가지 방법으로 바이너리 검색을 구현할 수 있습니다. 첫 번째는 반복입니다. 이 구현에서는 임시 루프를 사용할 것입니다.

function binarySearch( array, item) {
  //low and high are the range of indexes we're considering as part of our search section. 
  let low = 0
  let high = array.length-1
  //remember we are not discarding of anything in the array. We are just closing in on the target item. This while loop will go on until there is only 1 more item left to check in the array.
  while (low <= high) {
    let middle = Math.floor((low+high)/2)
    if (item > array[middle]) {
      low = middle+1
    }
    else if (item < array[middle]) {
      high = middle-1
    } 
    else if (item == array[middle])  {
      return middle
    }
    else return null
  }
}
//binary search algorithm returns either null, or the index at which the item is located

예를 들어볼 수 있을까요?

진정해, 내가 잡았어. 일종의 "분할 정복" 접근법입니다. 아래의 예를 살펴보십시오.

// we are searching for the item "fruit" in the inputted array
function binarySearch(
         ["apples", "bananas", "cows", "fruit", "zebra"],
                    "fruit") {
           //Because we are searching the entire array, we want the range of indexes considered to be 0 to (array.length-1) in other words, from the start of the array to the end
                let low = 0
                     let high = array.length-1 = 4
                     // because the low is less than the high, this means we have not closed in on our search item yet, and that there are still indexes left to check. We can proceed to the first iteration of this while loop 
                          while (low 0 <= high 4) {
                                      let middle = Math.floor((low+high)/2) = 2
                                      // because the item passed begins with the letter "f", and the item in the middle of the section we're searching starts with the letter "c", we can say that the item > array[middle] and enter this if statement below
                                                if (item "fruit" > array[middle] "cows") {
                                                  //here, we adjust for a new low. This is because we realized that the item we are searching for comes after the item we landed on. Therefore, we are now going to search from there to the end of the array. This means we have to adjust our range to start from the item afterrrr the one we landed on. 
                                                                  low = middle+1 = 2 + 1 = 3
                                                }
                                      else if (item < array[middle]) {
                                                        high = middle-1
                                      }
                                      else if (item == array[middle])  {
                                                         return middle
                                      }
                                      else return null
                          }
         }

 

// Below is the second and final iteration 
function binarySearch(
         ["apples", "bananas", "cows", "fruit", "zebra"],
                    "fruit") {
           // Remember, we adjusted for a new low -- 
           // After figuring out that the item we were looking for lays after the item in the middle, we are now searching from one item after the one in the middle, until the end of the array
                let low = 3
                     let high = array.length-1 = 4
                     //Since the low is still less than/ equal to the high, we can ease into another iteration of the while loop
                          while (low 3 <= high 4) {
                            let middle = Math.floor((low+high)/2) = Math.floor((3+4)/2) = 3
                                 if (item > array[middle]) {
                                             low = middle+1
                                 }
                                 else if (item < array[middle]) {
                                             high = middle-1
                                 }
                            // Because the item "fruit" is equal to the item located at array[middle], or array[3] ("fruit"), we will be exiting out of the while loop as we are returning the aforementioned position 
                                 else if (item "fruit" == array[middle] "fruit")  {
                                             return middle 3
                                 }
                                 else return null
                          }
         }
//The function above returns 3

재귀

바이너리 검색을 구현하는 두 번째 방법은 재귀 전략을 사용하는 것입니다. 재귀가 무섭긴 하지만 한번 해볼게

//Unlike the iterative approach, the recursive approach will take in 4 inputs: the array, the item in question, and the start and end indexes of the section we are searching in the array 
function binarySearchRecursive(array, item, start, end){
  //this is to make sure that the start and end values don't end up overlapping (remember we are closing in on our search item -- the start and end values provide the range of our focus)
      if (start > end) {
                return null
      }
      let middle = Math.floor((start + end)/2)
      //You can see that essentially the same thing is going on here and in our iterative approach. If the item is greater than the array[middle] value 
           if (item > array[middle]){
                        return binarySearchRecursive(array, item, middle+1, end)
           }
       else if (item < array[middle]){ 
                     return binarySearchRecursive(array, item, start, middle-
                                                              1)
       }
       else if (item == array[middle]){
                     return middle
       }
}

바이너리 검색을 선택해야 하는 이유

 

한 번에 하나의 항목씩 정렬된 거대한 배열을 탐색하는 것을 고려하고 있다면 이진 검색을 통해 실행 시간을 크게 단축하여 애플리케이션의 효율성을 최적화할 수 있습니다. 당신의 접근 방식에서, 당신은 데이터의 크기를 나타내는 N의 런타임을 가질 수 있는 반면, 이진 검색 알고리즘의 구현은 당신의 런타임 lognN을 배치할 것이다. 그래서, 만약 당신이 하나의 이름을 찾기 위해 128개의 알파벳 순서로 된 이름 목록을 넘나들 계획이었다면, 최악의 시나리오는 그 이름이 목록의 맨 아래에 있는 것이다. 목록을 하나씩 훑어본다면 그 이름을 손에 넣으려면 128단계나 걸어야 할 수 있다. 위에서 검토한 단계에 따라 바이너리 검색을 구현한 경우 해당 이름에 도달하는 데 7단계만 소요됩니다. 리스트가 두 배로 커졌다고 쳐요. 그 목록의 맨 아래에 도달하려면 256개의 단계를 거쳐야 합니다. 하나씩 이름을 살펴보면요. 바이너리 검색 구현에서는 이러한 단계를 8단계로 줄였습니다. 네, 목록을 두 배로 늘렸는데, 그 과정이 한 단계만 늘어났어요.

검색어:)