2022/03/21) 10. 이분검색 [정렬과 그리디, 결정알고리즘]

1. 문제

<이분검색>
: 임의의 N개의 숫자가 주어진다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개인 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성한다.

2. 해결 방법

1. 이분검색은 먼저 정렬을 한 다음에, 변수 lt와 rt, mid를 선언 후, 한 번의 비교를 통해서 검색범위를 절반으로 줄어들게 하는 것이다.
2. while문을 돌려서, mid값을 parseInt((lt+rt)/2) 해주고, 만약 arr[mid]값이 target과 같다면 이 break해주고, 다르다면 target보다 큰지 작은지 비교하여 arr[mid]값이 target보다 클 경우엔 rt값을 mid-1로 해주고, 작을 경우엔 lt값을 mid+1해준다. 정리하자면 값을 target과 비교해서, rt 혹은 lt 위치를 옮기는 것이다. mid를 기준으로 검색범위가 바뀌므로 거의 절반으로 줄어든다!

! parseInt와 Math.floor

• 둘 다 소수점을 버린다는 건 동일하지만, Math.floor는 내림이기 때문에 만약 -13.2라면 -14를 출력한다. parseInt는 -13으로 출력!

3. 정답

        <script>
            function solution(target, arr){
                let answer=0;
                arr.sort((a, b) => a-b); //정렬
                let lt = 0; rt = arr.length-1;
                while(lt <= rt){
                    let mid = parseInt((lt+rt)/2); //mid위치
                    if(arr[mid] === target){ 
                        answer = mid+1;
                        break;
                    }
                    else if(arr[mid] > target) rt=mid-1; //값을 target과 비교해서, rt혹은 lt위치 옮기기
                    else lt=mid+1;
                }
                return answer;
            }
            let arr=[23, 87, 65, 12, 57, 32, 99, 81];
            console.log(solution(32, arr));
        </script>

4. 내 코드와 비교 그리고 반성

나는 순차정렬로 코드를 짰다. for문으로 했는데 indexOf로 했으면 더 나았을 수도.. 근데 순차정렬은 시간복잡도가 0(n)이고, 이분검색은 0(logN)이라서 이분검색을 하면 시간이 반이나 줄어든다.

      <script>
          function solution(target, arr){
              let answer=0;
              arr.sort((a,b) => a-b);
              for(let i = 0; i < arr.length; i++ ){ //arr.indexOf(target) 해도 됨
                  if(arr[i] === target) answer = i+1;
              }
              return answer;
          }
          let arr=[23, 87, 65, 12, 57, 32, 99, 81];
          console.log(solution(32, arr));
      </script>