This post is part of a personal study group activity, summarizing the content after reading through the book "Grokking Algorithms".

In the IT field, an algorithm refers to code that embodies a method for solving a particular problem. A well-designed algorithm can process a problem far faster than a naive, straightforward approach. Since development involves an enormous variety of problems, and an even greater variety of ways to solve them, more complex problems demand more sophisticated algorithm design.

Because of this characteristic, algorithms demand strong problem-solving skills and mathematical thinking. This makes them one of the areas many people find difficult, but their power and efficiency also make them a useful measure of a developer's capability. The coding tests commonly used by companies are a good example of this.

This chapter explains how to use algorithms to improve the search operation more effectively. As mentioned in the previous chapter, the search operation is essentially just a large collection of read operations. Let's take a look at how algorithms optimize read operations.

A sorted array is an array in which the elements are arranged according to a specific ordering condition. In a sorted array, elements are always arranged in order according to a fixed rule. This applies during insertion as well. For a sorted array to always remain sorted, even when inserting, the element must be placed at the correct position that preserves the sort order without disrupting it.

With a regular array, as long as there's room in the array, you can insert anywhere you like. When inserting 55 into a normal array, there's no restriction on where it can go, as shown below.

But what about a sorted array? This time, let's assume the array is sorted in ascending order.

What happens if we insert 55 into this sorted array?

It must be inserted between 44 and 94 to preserve the ascending order. From this, we can infer that inserting into a sorted array requires additional logic compared to a regular insert operation. The principle is simple: we read through the elements sequentially, repeating until we find a number larger than 55. Since the array is sorted, once we encounter a number larger than 55, every element before it must be smaller than 55. We can insert at this position.

As shown above, we sequentially search through the elements to find one larger than 55. 94 is the smallest number in the array that's larger than 55.

We insert 55 at the index of 94, the 4th element, and shift 94 back by one position. Through this process, we can perform the operation on the sorted array.

So why go through all this extra trouble? The reason lies in search optimization. Because a sorted array inherently has the regularity of order, it becomes possible to apply algorithms that take advantage of that. This lets us effectively reduce the amount of work required for a search, enabling much faster searching.

JAVA
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;

/**
 * 누구나 자료 구조와 알고리즘 정렬된 배열 삽입 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/10/about-algorithm-chapter02/">알고리즘이 중요한 까닭</a>
 * @since 2021.07.10 Sat 02:41:14
 */
public class SortedArrayInsert
{
	// 배열
	private static final int[] ARRAY = { 6, 9, 14, 43, 94, -1, -1, -1, -1, -1 };
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 삽입할 요소
		int item = 55;
		
		int result = run(item);
		
		StringBuilder builder = new StringBuilder();
		builder.append(result);
		builder.append("번 째 인덱스에 ");
		builder.append(item);
		builder.append(" 삽입: ");
		builder.append(Arrays.toString(ARRAY));
		
		writer.write(builder.toString());
		writer.newLine();
		writer.flush();
		writer.close();
	}
	
	/**
	 * 집합 배열 삽입 및 삽입된 인덱스 반환 함수
	 *
	 * @param item: [int] 삽입할 요소
	 *
	 * @return [int] 삽입된 인덱스
	 */
	private static int run(int item)
	{
		int result = find(item);
		
		insert(result, item);
		
		return result;
	}
	
	/**
	 * 요소 검색 및 인덱스 반환 함수
	 *
	 * @param target: [int] 목표 숫자
	 *
	 * @return [int] 인덱스
	 */
	private static int find(int target)
	{
		// 인덱스
		int result = -1;
		
		for (int i = 0; i < ARRAY.length; i++)
		{
			// 목표 숫자보다 배열의 값이 클 경우
			if (target < ARRAY[i])
			{
				result = i;
				break;
			}
		}
		
		return result;
	}
	
	/**
	 * 배열 삽입 함수
	 *
	 * @param index: [int] 삽입 위치
	 * @param item: [int] 삽입할 요소
	 */
	@SuppressWarnings("ManualArrayCopy")
	private static void insert(int index, int item)
	{
		// 배열의 값이 -1(빈 요소)가 아닐 경우
		if (ARRAY[index] != -1)
		{
			for (int i = ARRAY.length - 1; i > index; i--)
			{
				ARRAY[i] = ARRAY[i - 1];
			}
		}
		
		ARRAY[index] = item;
	}
}

TC
4번 째 인덱스에 55 삽입: [6, 9, 14, 43, 55, 94, -1, -1, -1, -1]

The insert function is identical to the one from the previous chapter, but find has changed slightly. Instead of finding an identical value with target == ARRAY[i], it now finds a value larger than the item to insert with target < ARRAY[i]. The run function drives this process appropriately and returns the index at which insertion occurred.

JAVA's sort function
Java provides a function called Arrays.sort(), which takes the array to sort as its argument. By default, it sorts in ascending order, but you can override the sort function yourself to design your own custom sort order.

This is exactly the reason we sorted the array earlier. Applying an algorithm called binary search can dramatically improve search speed. In fact, binary search is one of the easier algorithms in the grand scheme of things. And you've likely already encountered binary search before, in a different form.

You've probably played a game called Up & Down as a kid, or maybe over drinks. The host picks an arbitrary number within some range in their head, and the participants try to guess it. When a participant says a number, the host tells them whether it's higher or lower than their number. This repeats until someone guesses correctly. The principle of binary search is exactly the same.

Due to its nature, binary search only works on a sorted array. Suppose we have an array sorted sequentially over the range 1 to 100. If the number we need to find is 68, binary search proceeds as follows.

1. Compare against 50, the midpoint of 1 and 100. (+1 operation)
2. Since 50 is less than 68, search the range 51 to 100.
3. Compare against 75, the midpoint of 51 and 100. (+1 operation)
4. Since 75 is greater than 68, search the range 51 to 74.
5. Compare against 62, the midpoint of 51 and 74. (+1 operation)
6. Since 62 is less than 68, search the range 63 to 74.
7. Compare against 68, the midpoint of 63 and 74. (+1 operation)
8. The search ends.

If we had searched sequentially, it would have taken a total of 68 operations to go from 1 up to 68 — but we completed the search in just 4 operations. Simply applying a simple algorithm reduced the workload by a factor of 17. The range here is small, but if the range extended into the tens of thousands, the workload would shrink exponentially, depending on the position of the number being searched for.

JAVA
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

/**
 * 누구나 자료 구조와 알고리즘 이진 검색 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/10/about-algorithm-chapter02/">알고리즘이 중요한 까닭</a>
 * @since 2021.07.10 Sat 03:24:26
 */
public class BinarySearch
{
	// 배열 최대 크기
	private static final int MAX = 100;
	
	// 배열
	private static final int[] ARRAY = initArray(MAX);
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 검색 대상
		int target = 68;
		
		int result = binarySearch(target);
		
		StringBuilder builder = new StringBuilder();
		builder.append(target);
		builder.append("을 탐색하는데 필요한 프로세스: ");
		builder.append(result);
		
		writer.write(builder.toString());
		writer.newLine();
		writer.flush();
		writer.close();
	}
	
	/**
	 * 배열 초기화 함수
	 *
	 * @param max: [int] 배열 최대 크기
	 *
	 * @return [int[]] 1 ~ max가 할당된 정수 배열
	 */
	private static int[] initArray(int max)
	{
		int[] temp = new int[max];
		
		for (int i = 0; i < max; i++)
		{
			temp[i] = i + 1;
		}
		
		return temp;
	}
	
	/**
	 * 이진 검색 및 프로세스 소요량 반환 함수
	 *
	 * @param target: [int] 검색 대상
	 *
	 * @return [int] 프로세스 소요량
	 */
	private static int binarySearch(int target)
	{
		// 프로세스 소요량
		int count = 0;
		
		// 중간값
		int mid = -1;
		
		// 구간 시작값
		int start = 1;
		
		// 구간 끝값
		int end = ARRAY.length;
		
		while (target != mid)
		{
			mid = (end + start) / 2;
			
			// 목표가 중간값보다 클 경우
			if (target > mid)
			{
				start = mid + 1;
			}
			
			// 목표가 중간값보다 작거나 같을 경우
			else
			{
				end = mid - 1;
			}
			
			count++;
		}
		
		return count;
	}
}

The source implementing binary search is shown above. The part worth paying attention to is the binarySearch function. The starting value start is initialized to 1, and the ending value max is equal to the size of the array.

We compute mid and compare its magnitude against target. If target is larger, it lies in the upper range relative to the midpoint, so we adjust start to mid + 1. Conversely, if target is smaller, it lies in the lower range relative to the midpoint, so we adjust end to mid - 1. We repeat the algorithm until the target value target equals the midpoint mid.

Since 1 through 100 are arranged in order, 1 is ARRAY[0] and 43 is ARRAY[42] — the value itself essentially acts as the index — so there's no need to compute the index separately.

JAVA
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

/**
 * 누구나 자료 구조와 알고리즘 이진 검색 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/10/about-algorithm-chapter02/">알고리즘이 중요한 까닭</a>
 * @since 2021.07.10 Sat 03:24:26
 */
public class BinarySearch
{
	// 배열 최대 크기
	private static final int MAX = 100;
	
	// 배열
	private static final int[] ARRAY = initArray(MAX);
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 검색 대상
		int target = 68;
		
		int result = binarySearch(target);
		
		StringBuilder builder = new StringBuilder();
		builder.append(target);
		builder.append("을 탐색하는데 필요한 프로세스: ");
		builder.append(result);
		
		writer.write(builder.toString());
		writer.newLine();
		writer.flush();
		writer.close();
	}
	
	/**
	 * 배열 초기화 함수
	 *
	 * @param max: [int] 배열 최대 크기
	 *
	 * @return [int[]] 1 ~ max가 할당된 정수 배열
	 */
	private static int[] initArray(int max)
	{
		int[] temp = new int[max];
		
		for (int i = 0; i < max; i++)
		{
			temp[i] = i + 1;
		}
		
		return temp;
	}
	
	/**
	 * 이진 검색 및 프로세스 소요량 반환 함수
	 *
	 * @param target: [int] 검색 대상
	 *
	 * @return [int] 프로세스 소요량
	 */
	private static int binarySearch(int target)
	{
		// 프로세스 소요량
		int count = 0;
		
		// 중간값
		int mid = -1;
		
		// 구간 시작값
		int start = 1;
		
		// 구간 끝값
		int end = ARRAY.length;
		
		while (target != mid)
		{
			count++;
			
			// 목표가 시간 구간 혹은 끝 구간과 일치할 경우
			if (target == start || target == end)
			{
				break;
			}
			
			mid = (end + start) / 2;
			
			// 목표가 중간값보다 클 경우
			if (target > mid)
			{
				start = mid + 1;
			}
			
			// 목표가 중간값보다 작거나 같을 경우
			else
			{
				end = mid - 1;
			}
		}
		
		return count;
	}
}

Binary search has a drawback: assuming a range of 1 to 100, values near the very start or end of the range, like 1 or 100, take a surprisingly long time to search for. This is a downside stemming from the fact that binary search always compares against the midpoint. The source above strengthens binary search by also comparing against the start and end of the range.

JAVA
// 목표가 시간 구간 혹은 끝 구간과 일치할 경우
if (target == start || target == end)
{
	break;
}

The part worth paying attention to is this section of the binarySearch function. New comparison logic against start and end, which wasn't there before, has been added, adjusting things so that the search becomes much faster when the target happens to be at the very start or end of the range.

An algorithm that searches sequentially, one by one starting from 1, is called linear search, while an algorithm that searches based on the midpoint of a range is called binary search. Over the course of this chapter, we designed both a standard array search and a binary search, and compared the difference between them.

With linear search, as the number of elements $N$ grows, the expected maximum workload grows proportionally to $N$ as well. Binary search, by comparison, has a maximum workload of 13 when $N = 10,000$, according to the book. When $N = 1,000,000$, the workload is only 20 — and considering that linear search's workload would be 1,000,000, we can see that the more data there is, the greater the expected savings binary search provides.

JAVA
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

/**
 * 누구나 자료 구조와 알고리즘 검색 퍼포먼스 비교 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/10/about-algorithm-chapter02/">알고리즘이 중요한 까닭</a>
 * @since 2021.07.10 Sat 04:21:37
 */
public class SearchCompare
{
	// 배열 최대 크기
	private static final int MAX = 100000000;
	
	// 배열
	private static final int[] ARRAY = initArray(MAX);
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 검색 대상
		int target = 86421478;
		
		long tic = System.nanoTime();
		
		int linearResult = find(target);
		
		long toc1 = System.nanoTime() - tic;
		
		tic = System.nanoTime();
		
		int binaryResult = binarySearch(target);
		
		long toc2 = System.nanoTime() - tic;
		
		StringBuilder builder = new StringBuilder();
		builder.append(target);
		builder.append("을 탐색하는데 소요된 선형 검색 프로세스: ");
		builder.append(linearResult);
		builder.append("(").append(toc1).append("ns)\n");
		builder.append(target);
		builder.append("을 탐색하는데 소요된 이진 검색 프로세스: ");
		builder.append(binaryResult);
		builder.append("(").append(toc2).append("ns)\n\n");
		builder.append("이진 검색이 약 ").append(toc1 / toc2).append("배 더 빠릅니다.");
		
		writer.write(builder.toString());
		writer.newLine();
		writer.flush();
		writer.close();
	}
	
	/**
	 * 배열 초기화 함수
	 *
	 * @param max: [int] 배열 최대 크기
	 *
	 * @return [int[]] 1 ~ max가 할당된 정수 배열
	 */
	private static int[] initArray(int max)
	{
		int[] temp = new int[max];
		
		for (int i = 0; i < max; i++)
		{
			temp[i] = i + 1;
		}
		
		return temp;
	}
	
	/**
	 * 이진 검색 및 프로세스 소요량 반환 함수
	 *
	 * @param target: [int] 검색 대상
	 *
	 * @return [int] 프로세스 소요량
	 */
	private static int binarySearch(int target)
	{
		// 프로세스 소요량
		int count = 0;
		
		// 중간값
		int mid = -1;
		
		// 구간 시작값
		int start = 1;
		
		// 구간 끝값
		int end = ARRAY.length;
		
		while (target != mid)
		{
			count++;
			
			// 목표가 시간 구간 혹은 끝 구간과 일치할 경우
			if (target == start || target == end)
			{
				break;
			}
			
			mid = (end + start) / 2;
			
			// 목표가 중간값보다 클 경우
			if (target > mid)
			{
				start = mid + 1;
			}
			
			// 목표가 중간값보다 작거나 같을 경우
			else
			{
				end = mid - 1;
			}
		}
		
		return count;
	}
	
	/**
	 * 요소 검색 및 인덱스 반환 함수
	 *
	 * @param target: [int] 목표 숫자
	 *
	 * @return [int] 인덱스
	 */
	private static int find(int target)
	{
		// 인덱스
		int result = -1;
		
		for (int i = 0; i < ARRAY.length; i++)
		{
			// 목표 숫자와 배열의 값이 일치할 경우
			if (target == ARRAY[i])
			{
				result = i;
				break;
			}
		}
		
		return result;
	}
}

TC
86421478을 탐색하는데 소요된 선형 검색 프로세스: 86421477(26936600ns)
86421478을 탐색하는데 소요된 이진 검색 프로세스: 26(5100ns)

이진 검색이 약 5281배 더 빠릅니다.

The source above combines linear search and binary search so their performance can be compared. It searches for an arbitrary number target within a range of 100,000,000 (100 million). In this source, that value is set to 86,421,478.

※ The above tests were run on an i7-10700K CPU with 32GB of RAM; results may vary depending on the runtime environment.

We can see that binary search can be up to roughly 5000 times faster than linear search. The units are $ms$ and $us$, so from a human perspective it might not feel like much of a difference, but from a machine's perspective, it's the equivalent of performing binary search 5000 times in the time it takes to perform linear search just once — a truly enormous difference.

In this chapter, I implemented binary search using an algorithm and compared it against a standard linear search, which really let me feel firsthand just how powerful algorithms can be.

I already knew from working in the field that algorithms were powerful, but implementing something this simple and comparing it directly really drove home why algorithms matter so much.

Normally, on a day off like today with tomorrow also off, I'd study until four or five in the morning — but between focusing on this the whole time and writing the post, I'm unusually exhausted....