이진 탐색

이진탐색이란?

-
-배열이 정렬 되어 있을 경우, 절반씩 줄여나가면서 탐색하면
적은 비용으로 탐색을 할 수 있다.

이진탐색의 효율성

1억개의 목록을 선형탐색 할 때, 1억번을 연산해야 하는데
이진 탐색으로 찾는다면 27번 안에 찾을 수 있다.

예제로 보는 이진 탐색

1. 이진 검색
   https://leetcode.com/problems/binary-search/
2. 회전 정렬된 배열 검색
   https://leetcode.com/problems/search-in-rotated-sorted-array/
3. 두 배열의 교집합
   https://leetcode.com/problems/intersection-of-two-arrays/

이진 탐색 구현

구현 순서 :
1. 시작,끝, 탐색 대상 배열을 인자로 받는 함수를 만든다
2. 중간 = 시작+끝 //2
3. 배열의 중간값이 찾는 값 비교, 작을때
-시작값 그대로, 끝 값 중간값-1
4. 클때
-시작값 : 중간값 +1
5. else : 중간값 리턴
6. 시작>중간 : return -1

bisect :빌트인 내장 함수

-빌트인 내장함수를 이용해서 이진 탐색을 할 수 있다.

bisect_left

정렬된 목록 내에서 숫자x의 맨 왼쪽 삽입 지점을 찾는데 사용된다.
bisect.bisect_left(nums:[],find:int) #찾는 값의 인덱스를 반환

#bisect 모듈 참고 
리턴 값인 i는 모든값이 내가 찾는 값보다 작다.
모든 요소들은 내가 찾는 값보다 작거나 크다 

찾는 값이 없는 경우: 리턴 값 검증 필요

1. 모든 값이 찾는 값보다 작다

bisect_left([-1,-2,-3],2) //3 반환 

2. 모든 값이 찾는 값보다 크다

bisect_left([-1,-2,-3],-4) //0 반환  

3. 찾는 값이 없고,찾는 값보다 작거나 큰 값이 존재

bisect_left([-1,-4,-5],-2) //2 반환 

**배열의 길이보다 반환 된 인덱스가 작은지, 해당 배열의 인덱스가 찾는 값인지 확인 해야 함

bisect_right

오른쪽 삽입 지점을 찾는데 사용.
bisect.bisect_right(nums:[],find:int)