정렬 된 배열에서 이진 검색을 사용하여 요소 찾기

난이도 쉽게
자주 묻는 질문 아마존 Apple 블룸버그 게시물에서 Facebook 구글 Microsoft 페이팔
배열 이진 검색조회수 371

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

정렬 된 배열이 주어지면 정렬 된 항목에서 이진 검색을 사용하여 요소 찾기 정렬. 존재하는 경우 해당 요소의 색인을 인쇄하고 그렇지 않으면 print -1을 인쇄하십시오.

입력

arr [] = {1, 6, 7, 8, 9, 12, 14, 16, 26, 29, 36, 37, 156}

X = 6 // 검색 할 요소

산출

색인 1에서 찾은 요소

정렬 된 배열에서 이진 검색을 사용하여 요소 찾기 방법

N 개의 요소가있는 정렬 된 배열 A가 주어지면 배열의 시작과 끝을 가리키는 Low 및 High 변수가있는 요소 X를 검색합니다. 이제 우리는 조건을 확인하고 낮고 높게 유지합니다. 낮음이 높음보다 큰 조건에 도달하면 루프를 종료합니다. 이진 검색은 어레이의 크기를 절반으로 줄이므로 로그온 시간이 복잡해집니다.

암호알고리즘

1. 최저가 최고보다 작거나 같을 때까지

ㅏ. Mid에서 Low + (High – Low) / 2로 설정
비. Mid 인덱스의 요소가 검색된 요소와 같으면 Mid를 반환합니다.
씨. Mid 인덱스의 요소가 검색된 요소보다 작 으면 오른쪽 배열에서 검색해야하므로 업데이트 Low = Mid + 1
디. Mid 인덱스의 요소가 검색된 요소보다 크면 왼쪽 배열에서 검색해야하므로 업데이트 High = Mid – 1

이것은 두 개의 변수 (낮음 및 높음)를 통해 검색 경계를 추적하는 반복적 인 절차입니다.

실시

정렬 된 배열에서 이진 검색을 사용하여 요소 찾기를위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int Binary_search(int arr[] , int X, int low ,int high)
{
  
  while(low <= high) // till low is less than high i.e. there is atleast one integer in the considered part of array
  {
    
    int mid = low + (high - low)/2; //compute the middle index
    
    if(arr[mid] == X) //if equal then return
      return mid;
      
    else if ( arr[mid] < X) //if smaller then increase the lower limit
      low = mid + 1;
      
    else //if larger then decrease the upper limit
    high = mid - 1;
  }
  return -1;
}
int main()
{
  int N,X;
  cin>>N>>X;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  int index = Binary_search(arr,X,0,N-1); //search for the element
  if(index >= 0)
    cout<<index<<endl;
  else
    cout<<-1<<endl;
  return 0;
}

정렬 된 배열에서 이진 검색을 사용하여 요소 찾기를위한 Java 프로그램

import java.util.Scanner;
class sum
{
    public static int Binary_search(int arr[] , int X, int low ,int high)
    {
      while(low <= high) // till low is less than high i.e. there is atleast one integer in the considered part of array
      {
        int mid = low + (high - low)/2; //compute the middle index
        if(arr[mid] == X) //if equal then return
          return mid;
        else if ( arr[mid] < X) //if smaller then increase the lower limit
          low = mid + 1;
        else //if larger then decrease the upper limit
        high = mid - 1;
      }
      return -1;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int index = Binary_search(a,x,0,n-1); //search for the element
        if(index >= 0)
          System.out.println(index);
        else
          System.out.println(-1);
    }
}
6 7
2 4 5 7 1 9
3

복잡성 분석

시간 복잡성

O (로그인) 여기서 n id는 배열의 크기입니다. 여기서 우리는 시작 및 끝 포인터를 고정하고 매번 그리고 first> end이면 루프를 중지합니다.

공간 복잡성

O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.

참조

균열 시스템 설계 인터뷰
Translate »