이분검색

코드

function solution(target, arr){
                let answer;
                arr.sort((a, b)=>a-b);
                let lt=0, rt=arr.length-1;
                while(lt<=rt){
                    let mid=parseInt((lt+rt)/2);
                    console.log("mid:", mid);
                    if(arr[mid]===target){
                        answer=mid+1;
                        break;
                    }
                    else if(arr[mid]>target) rt=mid-1;
                    else lt=mid+1;
                    console.log("lt:",lt,"rt",rt,"answer",answer);
                }
               
                return answer;
            }

            let arr=[23, 87, 65, 12, 57, 32, 99, 81];
            console.log(solution(12, arr));

원리

1. arr를 오름차순으로 정렬해준다.
2. arr의 중간(mid)을 정해준다.
   2-1. 투포인터인 lt,rt는 arr의 양끝에 지정해준다.
3. target이 중간(mid)보다 작을때는 rt가 mid보다 작은 값이므로 rt = mid-1로 정해준다.
4. target이 중간(mid)보다 클때는 lt가 mid보다 큰값이므로 lt = mid+1로 지정해준다.
5. target이 mid와 같다면 정답이므로 반복문을 탈출하고 답을 return한다.

알게된점

위와같은 방식으로 하면 시간을 획기적으로 줄일 수 있다.
arr.length가 작으면 for문을 돌려 하나하나 확인해도 되지만, arr.length가 1,000,000까지 가능하므로 너무 많은 수가 나오면 for문만으로는 시간초과가 된다.