క్రమబద్ధీకరించిన శ్రేణిలో బైనరీ శోధనను ఉపయోగించి మూలకాన్ని కనుగొనండి  


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ మైక్రోసాఫ్ట్ పేపాల్
అర్రే బైనరీ శోధన

సమస్యల నివేదిక  

క్రమబద్ధీకరించబడిన శ్రేణిని బట్టి, క్రమబద్ధీకరించబడిన బైనరీ శోధనను ఉపయోగించి మూలకాన్ని కనుగొనండి అమరిక. ఉన్నట్లయితే, ఆ మూలకం యొక్క సూచికను ముద్రించండి -1.

ఉదాహరణ  

ఇన్పుట్

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

X = 6 // మూలకం శోధించాలి

అవుట్పుట్

సూచిక 1 వద్ద మూలకం కనుగొనబడింది

క్రమబద్ధీకరించిన శ్రేణిలో బైనరీ శోధనను ఉపయోగించి ఎలిమెంట్‌ను కనుగొనండి  

N మూలకాలతో క్రమబద్ధీకరించబడిన శ్రేణి A ఇవ్వబడింది, శ్రేణి యొక్క ప్రారంభ మరియు ముగింపును సూచించే తక్కువ మరియు అధిక వేరియబుల్స్‌తో ఒక మూలకం X కోసం శోధిస్తుంది. ఇప్పుడు, మేము పరిస్థితులను తనిఖీ చేస్తాము మరియు తక్కువ మరియు అధికంగా నిర్వహిస్తాము. ఒకసారి మనం తక్కువ కంటే ఎక్కువ ఉన్న కండిషన్‌ను తాకితే లూప్‌ను ముగించండి. బైనరీ శోధన శ్రేణి యొక్క పరిమాణాన్ని సగానికి తగ్గిస్తుంది, అందుకే ఇది సమయం సంక్లిష్టతను లాగ్ చేయడానికి దారితీస్తుంది.

అల్గారిథం

1. తక్కువ వరకు తక్కువ లేదా అంతకంటే ఎక్కువ

a. తక్కువ + (అధిక - తక్కువ) / 2 కు మిడ్ సెట్ చేయండి
బి. మిడ్ ఇండెక్స్‌లోని మూలకం శోధించిన మూలకానికి సమానంగా ఉంటే, మిడ్‌ను తిరిగి ఇవ్వండి
సి. మిడ్ ఇండెక్స్‌లోని మూలకం శోధించిన మూలకం కంటే తక్కువగా ఉంటే, మనం సరైన శ్రేణిలో శోధించాల్సిన అవసరం కంటే, కాబట్టి తక్కువ = మధ్య + 1 ని నవీకరించండి
d. మిడ్ ఇండెక్స్‌లోని మూలకం శోధించిన మూలకం కంటే ఎక్కువగా ఉంటే, మనం ఎడమ శ్రేణిలో శోధించాల్సిన అవసరం కంటే, కాబట్టి హై = మిడ్ - 1 ని నవీకరించండి

ఇది కూడ చూడు
మరొక శ్రేణిని ఉపయోగించి మూలకాలను పెంచుకోండి

ఇది రెండు వేరియబుల్స్ (తక్కువ మరియు అధిక) ద్వారా శోధన సరిహద్దులను ట్రాక్ చేసే పునరుక్తి ప్రక్రియ.

అమలు  

క్రమబద్ధీకరించిన శ్రేణిలో బైనరీ శోధనను ఉపయోగించి ఎలిమెంట్‌ను కనుగొనడానికి సి ++ ప్రోగ్రామ్

#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;
}

క్రమబద్ధీకరించిన శ్రేణిలో బైనరీ శోధనను ఉపయోగించి మూలకాన్ని కనుగొనడానికి జావా ప్రోగ్రామ్

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

సంక్లిష్టత విశ్లేషణ  

సమయం సంక్లిష్టత

ఓ (లాగ్న్) ఇక్కడ n id శ్రేణి యొక్క పరిమాణం. ఇక్కడ మేము ప్రారంభ మరియు ముగింపు పాయింటర్‌ను పరిష్కరించాము మరియు ప్రతిసారీ మరియు మొదటి> ముగింపు ఉంటే లూప్‌ను ఆపండి.

ఇది కూడ చూడు
BST లీట్‌కోడ్ పరిష్కారంలో కనీస సంపూర్ణ వ్యత్యాసం

అంతరిక్ష సంక్లిష్టత

O (1) ఎందుకంటే మేము ఇక్కడ ఏ సహాయక స్థలాన్ని ఉపయోగించము.

ప్రస్తావనలు