정렬된 수에서 하나의 수의 위치 찾기

문제 정의

 

• 여러 개의 수가 정렬된 순서로 있을 때 특정한 수를 찾는 방법
• 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어짐
• 수가 정렬된 상태에서는 이진 탐색(binary search)을 활용하면 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있음

 

• 수의 예 : [12, 25, 31, 48, 54, 66, 70, 83, 95, 108]
• 83의 위치를 찾아보세요
• 88의 위치를 찾아보세요

 

---

해결 방법

 

• 수가 정렬된 상태이므로 중간의 값을 하나 선택한다.
• 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁힐 수 있다.
• 한번 비교 할때 마다 1/2씩 범위가 좁혀진다.

 

---

 

나의 시도... 실패.

 

while / if 조건들 수정 필요

left=0와 right=a.length 와 mid는 배열에 있는 요소 값이 아닌 배열에 몇 번째 위치인가를 나타내는 index값 이라는 개념 필요

배열의 mid 위치에 있는 값과 찾으려는 target의 값을 비교하려면 a [mid] == target 이런 식으로 비교!

 

---

 

개념 확립 및 솔루션

 

 

변수 선언

• 정렬된 배열 numbers
• 찾는 수 target
• 배열 맨 왼쪽 위치 표시 left
• 배열 맨 오른쪽 위치 표시 right
• 배열 중간 위치 표시 mid
• 배열 중간 mid 위치에 있는 데이터 값 표시 temp
• 찾는 수 있다 없다 해줄 boolean find   

 

 

 

right = length-1 

mid의 포인터  

멤버 변수 boolean 초기화 

체크!

 

---

 

 

While로 배열의 중간 값과 비교하여 target 찾도록 세팅

if로 찾는 값이 배열에 있는지 없는지 확인

 

 

 

 

while로 배열의 왼쪽부터 오른쪽 끝까지 돌릴 동안

같으면 찾았다 break / mid보다 크면 left 조정 / 작으면 right조정 -> 비교할 요소 수 절반으로 감소

mid와 temp 재정의 -> 새로운 mid 위치와 값 필요

 

마지막 출력할 때  0번째는 없으니까 mid++ 해주는 부분 

찾는 숫자 없을 경우도 "없다" 출력되도록 해주는 부분 체크!

 

while 조건

mid temp 재정의 

mid++

체크!

---

 

 

review

강의를 듣고 같이 풀어볼 때는 잘 됐는데
혼자 다시 풀어보려고 하니 막혔다.
어떤 개념이 부족한지를 찾아내고 그 부분을 더 공부하도록 해야겠다.

정렬된 수의 배열에서 특정 값을 찾을 경우 - 이진 탐색방법 추천! 속도 향상!
left/right/mid의 개념과 [ mid ]와 target을 비교
left/right/mid의 위치를 조정해나가며 찾는 방법으로 풀이
체크! 

2번째 알고리즘 문제 풀이 강의였다.
배열의 index의 개념이 부족했고,
무엇과 비교해야 되는지 조건식을 잘 못 세워서 실패하였다.
문제가 주어지면 큰 개념과 흐름을 파악하고
그것에 맞는 조건을 잘 세우는 것이 중요하다고 느꼈다.