#### 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.

- MID PRINT POS = SET POS = SET POS = SET POS = SET POS = SET

- 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]

#### 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 :

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

#### Binary Search Program using Recursion

#### C program

1. #include
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