정렬은 순서대로 요소를 숫자순, 문자순, 오름차순, 내림차순 등으로 재배열 하는 것이다.

많은 기본 알고리즘이 O(n^2)으로 돌아가고, 이는 코딩 테스트에서 사용되어선 안된다. 코딩 테스트
에서 정렬 알고리즘을 처음부터 구현할 필요도 없다. 대신 이진 탐색을 사용할 수 있도록 입력을 정렬해야 한다.

정렬된 배열에서 이진 탐색을 사용하면 O(n)보다 빠르게 검색을 수행할 수 있다.

시간 복잡도

기법

정렬된 인풋

만약 주어진 시퀀스가 정렬되어있다면 이진 탐색이 가장 먼저 해봐야 할 것이다.

제한된 범위의 인풋 정렬

계수 정렬은 미리 값의 범위를 알고 있을 경우 사용할 수 있다.

필수 문제

• LeetCode
  • Binary Search
  • Search in Rotated Sorted Array

추천 연습 문제

• LeetCode
  • Kth Smallest Element in a Sorted Matrix
  • Search a 2D Matrix
  • Kth Largest Element in an Array
  • Find Minimum in Rotated Sorted Array
  • Median of Two Sorted Arrays

참조
Do it 알고리즘 코딩 테스트 - Java 편
Array cheatsheet for coding interviews | Tech Interview Handbook