비전공자를 위한 컴퓨터공학 알고리즘 - 이진 검색

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

시리즈를 계속해 보자 

 

이 사이트에 다른 글도 많이 있으니 참조하시길

 

어차피 내가 귀찮게 링크 걸지 않아도 

 

알아서 좋은 거 알고 가져가실거라는거 알고 있다

 

 

자 순서대로 이진검색 코드를 분석해 보자 

 

 

 

바이너리 서치라는 함수를 이진검색이라는 함수를 배열과 타겟을 받는걸로 선언한다 

 

왼쪽은 0

 

오른쪽은 배열 길이를 놓고 싶은데 중앙에 한개를 선택했으므로 -1을 해놓는다. 

 

1 2 3   이 있을때  1 을 보자면 왼쪽은 0개있고 오른쪽에는 배열의 길이인 3개에서 -1개를 한 2개 2,3이 남는다

 

레프트가 라이트보다 작으면 와일문이기때문에 계속 반복문을 돌린다. 

 

중앙은 왼쪽과 오른쪽을 더해서 나눈 몫이다

 

/ 연산자가 아니라 // 연산자로 정수값만 반환하도록, 소수점 이하 값을 버리도록 한다 

 

 

 

 

만약에 배열의 중앙값이 타겟이라면 그냥 중앙값이 찾던 것이기 때문에 그것을 리턴하고 

 

그게 아니라 미드 값이 타겟보다 작다면 타겟은 중앙보다 오른쪽에 있을 것이므로, 

 

왼쪽 범위를 중앙+1 로 옮기므로서 범위를 줄여서 찾기 쉽도록 한다 

 

그게 아니라면 오른쪽 범위를 중앙 -1 로 옮기면서 범위를 줄인다 

 

찾지 못하면 -1을 반환한다

 

 

이후 코드는 아래와 같다 

 

위 내용도 이전글과 비슷하며 

 

선형검색에서 충분히 설명했던 내용이므로 굳이 설명하진 않겠다 

 

선형검색은 포문 하나로 주루룩 찾아간다면 

 

이진 검색은 와일문으로 주루룩 찾아가지만 

 

반씩 나눠서 찾아가는 방식이라는 점이 핵심이다 

 

반을 나누기 위해서는 중앙일 경우, 오른쪽일 경우, 왼쪽일 경우가 필요하다는 점이 특징이다

 

다음 글에서 또 만나자