# Binary Search

*Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].*

- Compare x with the middle element.
- If x matches with middle element, we return the mid index.
- 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.
- Else (x is smaller) recur for the left half.

# Search an element in a sorted and rotated array

*Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}; key = 3*

*Output : Found at index 8*

1) Find middle point **mid = (first_element + length)/2**

2) If key is present at middle point, return mid.** if (arr[mid] == key) return mid;**

3) Else If arr[l..mid] is sorted

- a) If key to be searched lies in range from arr[l]

to arr[mid], recur for arr[l..mid].

- b) Else recur for arr[mid+1..r]

4) Else (arr[mid+1..r] must be sorted)

- a) If key to be searched lies in range from arr[mid+1]

to arr[r], recur for arr[mid+1..r].

- b) Else recur for arr[l..mid]