1. Search

Linear Search

Works on any array.

How it works: Go through the entire array from left to right until you found the el. you want to find.

Runtime: $\mathcal{O}(n)$ because you might need to look at every el. of the array.

Binary Search

Works on sorted arrays.

public static int binarySearch(int x, int[] A) {
	int left = 0, right = A.length - 1;
	
	while (left <= right) {
		int mid = (left + right) / 2;
		if (A[mid] > target) right = mid - 1;
		else if (A[mid] < target) left = mid + 1;
		else return mid;
	}
	
	return -1;
}

How it works: Take the middle element. Check if it equals the el. you want to find. If it’s larger, go to the left, otherwise to the right (if the array is sorted ascending). Repeat recursively until you found the el.

Runtime: $\mathcal{O}(\log n)$ because you might need to split the array $\log n$ times.