Binary Search

1. In Binary Search technique, we search an element in a sorted array by recursively dividing the interval in half.

2. Firstly, we take the whole array as an interval.

3. If the Pivot Element (the item to be searched) is less than the item in the middle of the interval, We discard the second half of the list and recursively repeat the process for the first half of the list by calculating the new middle and last element.

4. If the Pivot Element (the item to be searched) is greater than the item in the middle of the interval, we discard the first half of the list and work recursively on the second half by calculating the new beginning and middle element.

5. Repeatedly, check until the value is found or interval is empty.

Analysis:

1. Input: an array A of size n, already sorted in the ascending or descending order.
2. Output: analyze to search an element item in the sorted array of size n.
3. Logic: Let T (n) = number of comparisons of an item with n elements in a sorted array.

• Set BEG = 1 and END = n
• Find mid =
• Compare the search item with the mid item.

Case 1: item = A[mid], then LOC = mid, but it the best case and T (n) = 1

Case 2: item ≠A [mid], then we will split the array into two equal parts of size .

And again find the midpoint of the half-sorted array and compare with search element.

Repeat the same process until a search element is found.

T (n) = ...... (Equation 1)

{Time to compare the search element with mid element, then with half of the selected half part of array}

At least there will be only one term left that's why that term will compare out, and only one comparison be done that's why

Is the last term of the equation and it will be equal to 1