Please describe briefly the procedure of Binary Search State

Please describe briefly the procedure of Binary Search. State its worst case running time, and
give the analysis how you can obtain such a bound.

Solution

Please find my analysis.

Please let me know in case of any issue.

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Logn).

We basically ignore half of the elements just after one comparison.
1) Compare x with the middle element.
2) If x matches with middle element, we return the mid index.
3) Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
4) Else (x is smaller) recur for the left half.

// A iterative binary search function. It returns location of x in
// given array arr[l..r] if present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = l + (r-l)/2;

// Check if x is present at mid
if (arr[m] == x)
return m;

// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;

// If x is smaller, ignore right half
else
r = m - 1;
}

// if we reach here, then element was not present
return -1;

}

Time Complexity:
   The time complexity of Binary Search can be written as
   T(n) = T(n/2) + c
   The above recurrence can be solved either using Recurrence T ree method or Master method. It falls in case II of Master Method and solution of the recurrence is O(Logn).