이진 검색에 대해 조금

알고리즘은 단계별로 잘 정의된 명령이 프로그램이나 작업을 수행하는 것입니다. 이진 검색은 흥미로운 알고리즘 종류이고 프로그램이나 작업의 고성능에 많은 도움이 되기 때문에 이진 검색에 대해 더 많이 작성하고 배우기로 선택했습니다.

전화 번호부에서 전화 번호를 찾고 있다고 가정하고 소유자 이름 전화는 L로 시작합니다. 중간에 전화 번호부를 열고 K 문자 전화 목록을 찾으면 K가 L 앞에 있다는 것을 알고 거의 절반을 제거합니다. 전화번호부 옵션.

수백만 명의 사용자가 있는 소셜 네트워크를 상상하고 F로 시작하는 사용자를 찾으려고 합니다. 사용자에 대한 검색을 시도할 때 F로 시작하고 모든 수백만 사용자를 대상으로 하는 소셜 네트워크 프로그래밍 검색은 불필요한 시간과 리소스를 소비합니다. .

📌 이진 검색은 검색을 수행하고 검색 옵션을 최소화하는 일종의 알고리즘입니다. 그러나 이것은 정렬된 목록에서만 작동한다는 것을 기억하십시오.

번호 검색

이제 배열에서 숫자 32를 검색한다고 가정합니다. 숫자 32가 중간에 가깝다는 것을 알고 42 숫자*를 반환하는 위치를 취합니다. 42*는 32보다 작으므로 반수를 제거할 수 있습니다.



이제 3개의 위치가 있는 배열을 가질 수 있고 다시 중간 위치를 취하면 20개의 숫자가 반환됩니다.



이제 20이 32보다 적으며 검색을 위해 하나의 숫자가 남았습니다. 32입니다!

실습

Dart 언어로 이진 검색을 작성하는 방법을 살펴보겠습니다. binarySearch 함수는 배열과 항목을 취하고 함수는 배열에서 항목의 위치를 ​​반환합니다.

void main() {
  const list = [5, 20, 32, 43, 65, 88];

  print(binarySearch(list, 32)); // 2
  print(binarySearch(list, -1)); // null
}

int? binarySearch(List<int> list, int item) {
  // low and high to track search
  var low = 0;
  var high = list.length - 1;

  while (low <= high) {
    // check the middle of element
    var middle = low + high;
    var guess = list[middle];

    // If found them
    if (guess == item) return middle;
    // The guess is fewest than item
    if (guess < item)
      low = middle + 1;
    // The guess is higher than item
    else
      high = middle - 1;
  }

  // The item does not exists
  return null;
}