- Binary Search in data structure in hindi
- BINARY_SEARCH(A, lower_bound, upper_bound, VAL)
- Complexity of binary search in hindi
- Example of binary search in hindi
- Binary Search Program using Recursion in hindi
- C program for binary search
- java program for binary search
- C# program for binary search
- python program for binary search
Binary Search in data structure in hindi
Binary search एक खोज तकनीक है जो क्रमबद्ध (sorted) सूचियों पर कुशलता से काम करती है। इसलिए, बाइनरी सर्च तकनीक का उपयोग करके किसी सूची में एक तत्व को खोजने के लिए, हमें यह सुनिश्चित करना चाहिए कि सूची को sort किया गया है।
Binary search विभाजन और conquer (जितना) तरिका अपनाता है, जिसमें सूची को दो हिस्सों में विभाजित किया जाता है और सूची के मध्य तत्व के साथ आइटम की तुलना की जाती है। यदि मैच पाया जाता है, तो मध्य तत्व का स्थान (location) जवाब में वापस आता है अन्यथा, हम मैच के माध्यम से उत्पन्न परिणाम के आधार पर दोनों हिस्सों में खोज करते हैं।
बाइनरी खोज एल्गोरिदम नीचे दिया गया है।
BINARY_SEARCH(A, lower_bound, upper_bound, VAL)
- Step 1: [INITIALIZE] SET BEG = lower_bound
END = upper_bound, POS = – 1 - Step 2: Repeat Steps 3 and 4 while BEG <=END
- Step 3: SET MID = (BEG + END)/2
- Step 4: IF A[MID] = VAL
SET POS = MID
PRINT POS
Go to Step 6
ELSE IF A[MID] > VAL
SET END = MID – 1
ELSE
SET BEG = MID + 1
[END OF IF]
[END OF LOOP] - Step 5: IF POS = -1
PRINT “VALUE IS NOT PRESENT IN THE ARRAY”
[END OF IF] - Step 6: EXIT
Complexity
SN | Performance | Complexity |
---|---|---|
1 | Worst case | O(log n) |
2 | Best case | O(1) |
3 | Average Case | O(log n) |
4 | Worst case space complexity | O(1) |
Example
Let us consider an array arr = {1, 5, 7, 8, 13, 19, 20, 23, 29}. Find the location of the item 23 in the array.
In 1st step :
- BEG = 0
- END = 8ron
- MID = 4
- a[mid] = a[4] = 13 < 23, therefore
in Second step:
- Beg = mid +1 = 5
- End = 8
- mid = 13/2 = 6
- a[mid] = a[6] = 20 < 23, therefore;
in third step:
- beg = mid + 1 = 7
- End = 8
- mid = 15/2 = 7
- a[mid] = a[7]
- a[7] = 23 = item;
- therefore, set location = mid;
- The location of the item will be 7.
Binary Search Program using Recursion in hindi
C program
- #include<stdio.h>
- int binarySearch(int[], int, int, int);
- void main ()
- {
- int arr[10] = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};
- int item, location=-1;
- printf(“Enter the item which you want to search “);
- scanf(“%d”,&item);
- location = binarySearch(arr, 0, 9, item);
- if(location != –1)
- {
- printf(“Item found at location %d”,location);
- }
- else
- {
- printf(“Item not found”);
- }
- }
- int binarySearch(int a[], int beg, int end, int item)
- {
- int mid;
- if(end >= beg)
- {
- mid = (beg + end)/2;
- if(a[mid] == item)
- {
- return mid+1;
- }
- else if(a[mid] < item)
- {
- return binarySearch(a,mid+1,end,item);
- }
- else
- {
- return binarySearch(a,beg,mid-1,item);
- }
- }
- return –1;
- }
Output:
Enter the item which you want to search 19 Item found at location 2
Java
- import java.util.*;
- public class BinarySearch {
- public static void main(String[] args) {
- int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};
- int item, location = –1;
- System.out.println(“Enter the item which you want to search”);
- Scanner sc = new Scanner(System.in);
- item = sc.nextInt();
- location = binarySearch(arr,0,9,item);
- if(location != –1)
- System.out.println(“the location of the item is “+location);
- else
- System.out.println(“Item not found”);
- }
- public static int binarySearch(int[] a, int beg, int end, int item)
- {
- int mid;
- if(end >= beg)
- {
- mid = (beg + end)/2;
- if(a[mid] == item)
- {
- return mid+1;
- }
- else if(a[mid] < item)
- {
- return binarySearch(a,mid+1,end,item);
- }
- else
- {
- return binarySearch(a,beg,mid-1,item);
- }
- }
- return –1;
- }
- }
Output:
Enter the item which you want to search 45 the location of the item is 5
C#
- using System;
- public class LinearSearch
- {
- public static void Main()
- {
- int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};
- int location=-1;
- Console.WriteLine(“Enter the item which you want to search “);
- int item = Convert.ToInt32(Console.ReadLine());
- location = binarySearch(arr, 0, 9, item);
- if(location != –1)
- {
- Console.WriteLine(“Item found at location “+ location);
- }
- else
- {
- Console.WriteLine(“Item not found”);
- }
- }
- public static int binarySearch(int[] a, int beg, int end, int item)
- {
- int mid;
- if(end >= beg)
- {
- mid = (beg + end)/2;
- if(a[mid] == item)
- {
- return mid+1;
- }
- else if(a[mid] < item)
- {
- return binarySearch(a,mid+1,end,item);
- }
- else
- {
- return binarySearch(a,beg,mid-1,item);
- }
- }
- return –1;
- }
- }
Output:
Enter the item which you want to search 20 Item found at location 3
Python
- def binarySearch(arr,beg,end,item):
- if end >= beg:
- mid = int((beg+end)/2)
- if arr[mid] == item :
- return mid+1
- elif arr[mid] < item :
- return binarySearch(arr,mid+1,end,item)
- else:
- return binarySearch(arr,beg,mid-1,item)
- return –1
- arr=[16, 19, 20, 23, 45, 56, 78, 90, 96, 100];
- item = int(input(“Enter the item which you want to search ?”))
- location = –1;
- location = binarySearch(arr,0,9,item);
- if location != –1:
- print(“Item found at location %d” %(location))
- else:
- print(“Item not found”)
Output:
Enter the item which you want to search ? 96 Item found at location 9 Enter the item which you want to search ? 101 Item not found
Binary Search function using Iteration in hindi
- int binarySearch(int a[], int beg, int end, int item)
- {
- int mid;
- while(end >= beg)
- {
- mid = (beg + end)/2;
- if(a[mid] == item)
- {
- return mid+1;
- }
- else if(a[mid] < item)
- {
- beg = mid + 1;
- }
- else
- {
- end = mid – 1;
- }
- }
- return –1;
- }