Binary Searching

Binary Searching

Binary search is a search technique that performs well on sorted lists. As a result, in order to use the binary search strategy to find an element in a list, we must first confirm that the list is sorted.

Binary search employs a divide-and-conquer strategy, in which the list is split in half and the item is compared to the list's middle element. If a match is found, the middle element's position is returned; otherwise, we search into one of the halves based on the match's outcome.

The following is a description of the binary search algorithm.

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

  • [INITIALIZE] is the first step. SET POS = -1, BEG = lower bound, END = upper bound
  • Step 2: While BEG=END, repeat steps 3 and 4 twice more.
  • SET MID = (BEG + END)/2 as the third step.
  • IF A[MID] = VAL (Step 4)
  • MID PRINT POS = SET POS = SET POS = SET POS = SET POS = SET
  • Continue to Step 6.
  • IF A[MID] > VAL, THEN
  • SET BEG = MID + 1 ELSE [END OF IF] [END OF LOOP] SET END = MID - 1
  • Step 5: PRINT "VALUE IS NOT PRESENT IN THE ARRAY" IF POS = -1 [END OF IF]
  • EXIT is the sixth step.

Complexity

Sr.No Performance Complexity
l. Worst case O(log n)
2. Best case O(1)
3. Average Case O(log n)
4. Worst case space complexity O(1)

In 1st step :

  1. END = 8ron BEG = 0
  2. MEDIAN = 4
  3. a
  4. Because [mid] = a[4] = 13 23 in the second step:
  5. Start = mid+1 = 5 End = 8 mid = 13/2 = 6 a
  6. Because [mid] = a[6] = 20 23 at the third step, begin = mid + 1 = 7 and end = 8 mid = 15/2 = 7
  7. a
  8. [mid] = a[7] a[7] a[7] a[7] a[7] a[7] a[7] a[7]
  9. As a result, set location = mid; the item's location will be 7.

Binary Search Program using Recursion

C program

1. #include<stdio.h> 2. int binarySearch(int[], int, int, int); 3. void main () 4. { 5. int arr[10] = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100}; 6. int item, location=-1; 7. printf("Enter the item which you want to search "); 8. scanf("%d",&item); 9. location = binarySearch(arr, 0, 9, item); 10. if(location != -1) 11. { 12. printf("Item found at location %d",location); 13. } 14. else 15. { 16. printf("Item not found"); 17. } 18. } 19. int binarySearch(int a[], int beg, int end, int item) 20. { 21. int mid; 22. if(end >= beg) 23. { 24. mid = (beg + end)/2; 25. if(a[mid] == item) 26. { 27. return mid+1; 28. } 29. else if(a[mid] < item) 30. { 31. return binarySearch(a,mid+1,end,item); 32. } 33. else 34. { 35. return binarySearch(a,beg,mid-1,item); 36. } 37. 38. } 39. return -1; 40. } Enter the item which