BINARY SEARCH
WHAT IS BINARY SEARCH? Binary Search is defined as a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N). HOW BINARY SEARCH WORKS ? Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and the target = 23. First Step: Initially the search space is from 0 to 9. Let’s denote the boundary by L and H where L = 0 and H = 9 initially. Now mid of this search space is M = 4. So compare target with arr[M]. Second Step: As arr[4] is less than target, switch the search space to the right of 16, i.e., [5, 9]. Now L = 5, H = 9 and M becomes 7. Compare target with arr[M]. Third Step: arr[7] is greater than target. Shift the search space to the left of M, i.e., [5, 6]. So, now L = 5, H = 6 and M = 6. Compare arr[M] with target. Here arr[M] and tar...