Binary Search 알고리즘 (JS)

Binary Search

사전 지식
정렬된 array를 보다 효율적인 time Complexity로 해결하고자 할 때 사용하는 알고리즘
** O(n) = O(logn)
언제 쓰나?
정렬된 배열에서 원하는 값을 찾고자 할 때
pivot
첫과 끝 인덱스의 합을 나눠 중간값으로 사용하는 변수
sort

O(n) = O(nlogn)

stable & unstable
stable ? merge sort
unstable ? quick,heap sort
정렬이후 정렬이 유지되는 경우 stable,
정렬이후 일관성이 깨지는 경우 unstable,

const needSort = [{age:3,name:"A"},{age:3,name:"B"},{age:3,name:"C"},{age:4,name:"D"},{age:5,name:"F"}];

다음과 같은 배열을 age로 정렬했을 때, age가 3인 경우 주어지는 value "A","B","C"가 정렬 이후 유지되면 stable,
아니라면 unstable
관련문제

풀이

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
 let startIdx = 0;
 let endIdx = nums.length-1;
 while(startIdx<=endIdx){
     let pivot = Math.floor((startIdx+endIdx)/2);
     if(nums[pivot]===target){
         return pivot;
     }else if(nums[pivot]<target){
         startIdx = pivot + 1;
     }else{
         endIdx = pivot - 1;
     }
 }   
 return -1;
};