सॉर्ट की गई सरणी में बाइनरी सर्च का उपयोग करके तत्व खोजें


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना सेब ब्लूमबर्ग Facebook गूगल माइक्रोसॉफ्ट पेपैल
ऐरे द्विआधारी खोज

समस्या का विवरण

एक क्रमबद्ध सरणी को देखते हुए, क्रमबद्ध में द्विआधारी खोज का उपयोग करने वाले तत्व का पता लगाएं सरणी। यदि मौजूद है, तो उस तत्व के सूचकांक को प्रिंट करें -1।

उदाहरण

निवेश

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

X = 6 // खोजा जाने वाला तत्व

उत्पादन

सूचकांक 1 पर पाया गया तत्व

सॉर्ट किए गए एरियर में बाइनरी सर्च का उपयोग करके एलीमेंट का पता लगाएं

एन तत्वों के साथ एक सॉर्ट किए गए ए को देखते हुए, एरे के शुरुआती और अंत की ओर इशारा करते हुए निम्न और उच्च चर वाले तत्व एक्स की खोज। अब, हम स्थितियों की जाँच करते हैं और निम्न और उच्च को बनाए रखते हैं। एक बार जब हम उस स्थिति से टकराते हैं जिसमें कम उच्च से अधिक होता है तो लूप को समाप्त करें। द्विआधारी खोज सरणी के आकार को आधे से कम कर देता है यही कारण है कि यह हमें लॉग इन टाइम जटिलता की ओर ले जाता है।

कलन विधि

1. जब तक लो हाई के बराबर या उससे कम न हो

ए। मध्य से निम्न + (उच्च - निम्न) / 2 पर सेट करें
बी यदि मिड इंडेक्स में तत्व सर्च किए गए एलिमेंट के बराबर है, तो मिड वापस लौटें
सी। यदि मिड इंडेक्स में तत्व सर्च किए गए एलिमेंट से कम है, तो हमें सही एरे पर सर्च करने की जरूरत है, इसलिए लो = मिड + 1 अपडेट करें
डी अगर मिड इंडेक्स में तत्व सर्च किए गए एलिमेंट से ज्यादा है, तो हमें लेफ्ट एरे पर सर्च करना है, इसलिए हाई = मिड - 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

जटिलता विश्लेषण

समय जटिलता

O (लोगन) जहां n सरणी का आकार आईडी है। यहां हमने हर बार स्टार्ट और एंड पॉइंटर को ठीक किया और पहले> एंड के बाद लूप बंद कर दिया।

अंतरिक्ष जटिलता

ओ (1) क्योंकि हम यहाँ किसी भी सहायक स्थान का उपयोग नहीं करते हैं।

संदर्भ