이진 검색이란 무엇이며 사용하는 이유는 무엇입니까?

이진 검색은 검색 알고리즘입니다. 정렬된 배열에서 특정 숫자의 위치, 정렬된 문자열에서 문자를 효율적으로 검색하는 데 사용됩니다. 또한 요소의 첫 번째 항목 또는 마지막 항목을 검색하는 데 사용할 수도 있습니다. 가장 중요한 것은 정렬된 배열이나 문자열의 경우에만 사용할 수 있다는 것입니다.

논리

처음에는 중간 위치를 다음과 같이 계산합니다.

int s = 0, e = the length of array or string.
int mid = (s+e)/2;

이제 mid가 있으면 3개의 경우가 있습니다. 가운데에 있는 요소가 우리가 찾고 있는 요소(X라고 합시다)보다 크거나 작은지 확인합니다.

사례 1: arr[mid]>X

그러면 mid 뒤의 요소도 X보다 크다는 것을 의미합니다. 따라서 검색할 배열을 s to mid 에서 줄일 수 있습니다. 그래서 우리는 e=mid-1 ;

사례 2: arr[mid]<X

그러면 mid 앞의 요소도 X보다 작다는 것을 의미합니다. 따라서 mid + 1 to e 검색에서 배열을 줄일 수 있습니다. 그래서 우리는 s=mid+1 ;

사례 3: arr[mid]==X

우리가 마침내 X의 위치를 ​​얻었을 때.

다음은 어떻게 작동하는지 보여주는 코드입니다.

int binarySort(int arr[],int X){
  int arr=[1,2,3,4,5,6,7,8,9]; // A sorted Array of length n
  int s = 0,e = n-1;

  while(s<=e){
   int mid = (s+e)/2;
   if(arr[mid] > X) e = mid - 1;
   else if (arr[mid] < X) s = mid + 1;
   else return mid;
  }
  return -1;
}

첫 번째 항목 또는 마지막 항목을 찾으려면

X의 위치를 ​​찾을 때 First Occurrence와 Last Occurrence에 대한 새로운 조건이 필요합니다.

첫 번째 발생:

중간 - 1 위치에 동일한 요소가 있는지 확인하십시오. 그렇다면 검색 공간을 줄여야 합니다. First Occurrence의 경우 Mid + 1 Position Last Occurrence의 경우

   else{
     if(arr[mid-1] != arr[mid] or mid == 0)
          return mid;
     else 
          e = mid - 1;

   }

마지막 발생:

mid + 1 위치에 동일한 요소가 있는지 확인하고 그렇다면 검색 공간을 줄여야 합니다.
s = mid+1로 만듦으로써;

   else{
     if(arr[mid+1] != arr[mid] or mid == n-1)
          return mid;
     else 
          s = mid + 1;

   }

추가할 사항이 있으면 의견에 제안하십시오.