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

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

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