Binary Search

Notation

$\Omega (1)$

$\theta (log(n))$

$O(log(n))$

Step by Step

1. List is sorted

2. Divide the list into two

3. Divide the half with what you want into two

4. Repeat 2 and 3 until found

Pseudocode

arr = list
t = target value

int binarySearch(int arr[], int start, int end, int t)
{
    if (end >= start) {
        int mid = start + (end - start) / 2;

        // itself
        if (arr[mid] == t)
            return mid;
 
        // if smaller check left
        if (arr[mid] > t)
            return binarySearch(arr, start, mid - 1, t);
				// if bigger check right				
				else
						return binarySearch(arr, mid + 1, end, t);
    }
}

Video