이진 검색

알고리즘은 문제를 해결하기 위한 일련의 지침입니다. 독자에게 식사 준비를 위한 특정 단계를 알려주는 요리책의 레시피와 같은 알고리즘을 생각할 수 있습니다. 다양한 유형의 알고리즘이 있습니다. 그중 하나는 배열을 통해 검색하는 것으로 검색 알고리즘이라고 합니다. 이러한 검색 알고리즘 중 하나를 이진 검색이라고 합니다.

이진 검색의 주요 포인트는 정렬된 배열에서 요소의 위치를 ​​찾는 것입니다. 이진 검색은 분할 및 정복 접근 방식으로 문제를 해결합니다. 답을 얻을 수 있는 가장 작은 가능성으로 문제를 나눈다는 의미입니다. 첫 번째 단계는 검색을 수행할 배열을 갖는 것입니다.



값 4를 찾아봅시다. 포인터 2개를 설정해야 합니다. 하나의 포인터는 낮음이라고 하며 가장 낮은 위치에 놓이고 다른 하나는 높음이라고 하며 가장 높은 위치에 놓입니다.



또한 배열에서 중간 요소를 찾아야 합니다. mid라는 변수를 만들고 가장 낮은 인덱스와 가장 높은 인덱스의 합계와 같게 한 다음 합계를 2로 나눌 수 있습니다. 이렇게 하면 배열의 중간 위치를 알 수 있습니다: arr[(low + high)/2] = 6


이제 찾고자 하는 값이 중간인지, 중간보다 작은지, 중간보다 큰지 확인해야 합니다. mid와 같으면 mid를 반환합니다. 찾고 있는 값이 더 크면 low 를 low = mid + 1 로 바꿉니다. 중간 인덱스 이후 배열의 인덱스에 초점을 맞추고 있음을 의미합니다. 값이 mid보다 작으면 high를 high = mid + 1로 대체합니다. 여기서 중간 위치 이전의 요소에 초점을 맞춥니다.



낮은 값이 높은 값을 만날 때까지 또는 값을 찾을 때까지 이 단계를 반복합니다.



대단하다!!!!!! 4개를 찾았습니다



의사 코드:

do until the pointers low and high meet each other.
    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid]) // x is on the right side
        low = mid + 1
    else                       // x is on the left side
        high = mid - 1

JavaScript의 코드:

// Program to implement iterative Binary Search


// A iterative binary search function. It returns
// location of x in given array arr[low..high] is present,
// otherwise false

 function binarySearch(arr, x)
{   
    let low = 0;
    let high = arr.length - 1;
    let mid;
    while (high <= low) {
         mid = Math.floor((high - low) / 2);

        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;

        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            high = mid - 1;

        // Else the element can only be present
        // in right subarray
        else
            low = mid + 1;
    }

    // We reach here when element is not
    // present in array
    return false;
}