Binary search

When we want to determine whether an array contains a certain value (target), we usually need to iterate through the array to look at each element:

int[] array = {2, 4, 6, 10, 2, 5, 7, 9};
int targetValue = 9;
for(int i = 0; i < array.length; i++) {
  if(array[i] == targetValue) {
    System.out.println("Element matches target value at index: " + i);
	break;
  }
}

However, if the elements in the array are sorted, we can actually find the target value without looking at each element in the array. With an array that is sorted (say, in ascending order), we can check the element in the middle of the array. If the middle element's value equals the target, then we have successfully determined that the array contains the target value; otherwise we compare the element's value with the target value. If the element's value is greater than the target, then the target can only exist in the first half of the array (since it is sorted). Similarly, if the middle element's value is lower than the target , then the target can only exist in the second half of the array. In either case, we reduce our search space by half. We can further repeat this process and reduce our search space every time we look at the middle element in our search space. This process is called binary search, and it is a very efficient way to search for values in large arrays. (We will discuss more about efficiency at later chapters.)

Matrix Multiplication

In matrix (linear) algebra, one common thing to do is to multiply two matrices together. For example, if we have two matrices, A and B, as follows:

int[][] A = {{1, 3, 6},
             {2, 5, 4}};
int[][] B = {{0, 7},
             {-1, -2},
             {-3, -4}};

then the matrix multiplication of A and B is {{1 * 0 + 3 * -1 + 6 * -3, 1 * 7 + 3 * -2 + 6 * -4},{2 * 0 + 5 * -1 + 4 * -3, 2 * 7 + 5 * -2 + 4 * -4}} = {{-21, -23},{-17, -12}}. To implement the algorithm for matrix multiplication, we actually need 3 nested loops: 2 loops for each row/columns of the resultant matrix, and one loop for calculating the value at each cell of the resultant matrix.

Matrix Rotation

Another thing we can do with a matrix is to rotate it. For example with a matrix A: {{1, 3, 6},{2, 5, 4}}, we can rotate it clockwise so that it becomes {{2, 1},{5, 3},{4, 6}}. To achieve that, we need to create a new matrix to store the resultant rotated matrix (note that its dimensions will be flipped with respect to A), and use 2 nest loops to loop through elements in matrix A to populate the resultant matrix.

Convolution

Convolution is an important operation in image processing. It is an operation that takes as inputs: a matrix representing the bitmap of an image, and 3x3 kernel matrix, and a particular point in the image (row and column indices x and y). The operation slices out a 3x3 sub-matrix from the image matrix centered on position (x, y), performs a product on each number in the sub-matrix with the numbers at the corresponding positions in the kernel matrix, and then sums up all the product. For example, if the sub-matrix is : {{a, b, c},{d, e, f},{g, h, i}} and the kernel matrix is {{j, k, l},{m, n, o}, {p, q, r}}, then the convolution would be a * j + b * k + c * l + d * m + e * n + f * o + g * p + h * q + i * r. (If the position (x, y) is on the edge of the image matrix, we treat out-of-bounds positions in the sub-matrix as 0). When calculating convolution, we need to be careful about checking for potentially out-of-bound indices.