이진 검색: 정렬된 배열에서 타겟을 찾는 검색 알고리즘

• 이진 탐색 트리: 정렬된 구조를 저장하고 탐색하는 자료구조
• 이진 검색: 정렬된 배열에서 값을 찾아내는 알고리즘

65. 이진 검색

정렬된 nums를 입력받아 이진 검색으로 target에 해당하는 인덱스를 찾아라.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

• All the integers in nums are unique.

풀이 1. 재귀 풀이