ऐरे में बाइनरी खोज

Question

मैं केवल एक सरणी का उपयोग करके बाइनरी खोज को कैसे कार्यान्वित करूं?

Answer 1

सुनिश्चित करें कि आपकी सरणी को क्रमबद्ध किया गया है क्योंकि यह एक बाइनरी खोज का क्रूक्स है।

कोई अनुक्रमित/यादृच्छिक-पहुंच डेटा संरचना द्विआधारी खोजी जा सकती है। तो जब आप "केवल एक सरणी" का उपयोग करते हुए कहते हैं, तो मैं कहूंगा कि सरणी सबसे बुनियादी/सामान्य डेटा संरचना है जो एक बाइनरी खोज पर नियोजित है।

आप इसे रिकर्सिव (सबसे आसान) या इसके बाद से कर सकते हैं। बाइनरी खोज की समय जटिलता ओ (लॉग एन) है जो ओ (एन) में प्रत्येक तत्व की जांच करने की रैखिक खोज से काफी तेज है। यहाँ Wikipedia: Binary Search Algorithm से कुछ उदाहरण हैं:

रिकर्सिव:

BinarySearch(A[0..N-1], value, low, high) { 
    if (high < low) 
     return -1 // not found 
    mid = low + ((high - low)/2) 
    if (A[mid] > value) 
     return BinarySearch(A, value, low, mid-1) 
    else if (A[mid] < value) 
     return BinarySearch(A, value, mid+1, high) 
    else 
     return mid // found 
    } 

Iterative:

BinarySearch(A[0..N-1], value) { 
    low = 0 
    high = N - 1 
    while (low <= high) { 
     mid = low + ((high - low)/2) 
     if (A[mid] > value) 
      high = mid - 1 
     else if (A[mid] < value) 
      low = mid + 1 
     else 
      return mid // found 
    } 
    return -1 // not found 
} 

Answer 2

एकल तुलना संस्करण तेजी से और संक्षिप्त है

int bsearch_double(const double a[], int n, double v) { 
    int low = 0, mid; 
    while (n - low > 1) { 
    mid = low + (n - low)/2; 
    if (v < a[mid]) n = mid; 
    else   low = mid; 
    } 
    return (low < n && a[low] == v) ? low : -1; 
} 

Answer 3

यह निर्भर करता है अगर आप पुनरावृत्ति है आपकी सरणी में एक तत्व या नहीं और यदि आप कई निष्कर्षों की परवाह करते हैं या नहीं। मेरे पास इस कार्यान्वयन में दो विधियां हैं। उनमें से एक केवल पहली खोज देता है, लेकिन दूसरा कुंजी के सभी निष्कर्ष देता है।

import java.util.Arrays; 

public class BinarySearchExample { 

    //Find one occurrence 
    public static int indexOf(int[] a, int key) { 
     int lo = 0; 
     int hi = a.length - 1; 
     while (lo <= hi) { 
      // Key is in a[lo..hi] or not present. 
      int mid = lo + (hi - lo)/2; 
      if  (key < a[mid]) hi = mid - 1; 
      else if (key > a[mid]) lo = mid + 1; 
      else return mid; 
     } 
     return -1; 
    } 

    //Find all occurrence 
    public static void PrintIndicesForValue(int[] numbers, int target) { 
     if (numbers == null) 
      return; 

     int low = 0, high = numbers.length - 1; 
     // get the start index of target number 
     int startIndex = -1; 
     while (low <= high) { 
      int mid = (high - low)/2 + low; 
      if (numbers[mid] > target) { 
       high = mid - 1; 
      } else if (numbers[mid] == target) { 
       startIndex = mid; 
       high = mid - 1; 
      } else 
       low = mid + 1; 
     } 

     // get the end index of target number 
     int endIndex = -1; 
     low = 0; 
     high = numbers.length - 1; 
     while (low <= high) { 
      int mid = (high - low)/2 + low; 
      if (numbers[mid] > target) { 
       high = mid - 1; 
      } else if (numbers[mid] == target) { 
       endIndex = mid; 
       low = mid + 1; 
      } else 
       low = mid + 1; 
     } 

     if (startIndex != -1 && endIndex != -1){ 
      System.out.print("All: "); 
      for(int i=0; i+startIndex<=endIndex;i++){ 
       if(i>0) 
        System.out.print(','); 
       System.out.print(i+startIndex); 
      } 
     } 
    } 

    public static void main(String[] args) { 

     // read the integers from a file 
     int[] arr = {23,34,12,24,266,1,3,66,78,93,22,24,25,27}; 
     Boolean[] arrFlag = new Boolean[arr.length]; 
     Arrays.fill(arrFlag,false); 

     // sort the array 
     Arrays.sort(arr); 

     //Search 
     System.out.print("Array: "); 
     for(int i=0; i<arr.length; i++) 
      if(i != arr.length-1){ 
       System.out.print(arr[i]+","); 
      }else{ 
       System.out.print(arr[i]); 
      } 

     System.out.println("\nOnly one: "+indexOf(arr,24)); 
     PrintIndicesForValue(arr,24); 

    } 

} 

अधिक जानकारी के लिए कृपया https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/BinarySearchExample.java जाएँ। मुझे उम्मीद है यह मदद करेगा।