문제 링크
https://leetcode.com/problems/search-insert-position/
이진 탐색이란
Up & Down 게임처럼 특정 기준을 주고 up이면 그 이상에서 탐색하고 down이면 그 이하에서 탐색하는 방법무조건 정렬이 된 상태에서 해야한다완전 처음부터 탐색하는 배열의 O(n)과 달리 O(log n)의 시간복잡도가 소요되므로 효율성이 더 뛰어나다
소스 코드
function searchInsert(nums: number[], target: number): number {
let left = 0;
let right = nums.length - 1;
while(left <= right) {
let mid = Math.floor((left + right) / 2);
let midValue = nums[mid];
if(midValue === target) return mid
if(midValue < target) left = mid + 1;
else right = mid -1;
}
return left;
};
left와 right 의 인덱스를 초기화 해준다left는 0번 인덱스 right는 제일 마지막 인덱스중간 인덱스에 해당하는 값과 target의 값을 계속 비교해준다만약 target이 중간 인덱스 값보다 크면 왼쪽 인덱스를 +1 해준다중간 인덱스보다 작으면 오른쪽 인덱스를 -1해준다중간 인덱스는 왼쪽 또는 오른쪽 인덱스가 변경될때마다 다시 재할당을 해준다계속 반복하다가 중간인덱스의 값과 타겟의 값이 일치하면 곧바로 그 인덱스를 리턴해준다일치하지 않으면 left를 리턴해준다 ( 일치하는 값이 없을때 리턴된다 )