이분 탐색은 배열의 요소들이 정렬된 상태에서 탐색하는 아주 빠른 방법.

• 이분 탐색의 시간복잡도는 O(logN) ex) 배열의 요소가 8개이면 log8 = 3 즉 최소 3번만에 원하는 값을 찾는다.

이분 탐색 구현

let target = 32; // 32가 몇번째 있는지 찾을거임.

let arr = [23,87,65,12,57,32,99,81] // 정렬되지 않은 배열

arr.sort((a,b)=>a-b); // arr 배열을 내림차순 정렬을 한다.

let lt = 0; // 배열의 좌측 끝 값의 인덱스.
let rt = arr.length-1; // 배열의 우측 끝 값의 인덱스.

while(lt <= rt){
let mid = parseInt((lt+rt)/2); // 배열의 중간 인덱스.

	if(arr[mid] == target){ // 중앙값이 타켓이랑 같으면 
		 answer = mid + 1; // answer는 mid 인덱스 + 1  = 번째 수
			break; // target을 찾있디면 반복문 그만 돌려라.

	}else if(arr[mid] > target){ // 중앙값이 타겟 값보다 크면, 
		rt = mid - 1; // 우측 끝 값의 인덱스를 현재 mid의 바로 전, mid -1 인덱스로 초기화

	}else lt= mid +1; // 중앙 값이 타겟 값보다 작으면, 좌측 끝값의 인덱스를 현재 mid의 바로다음 으로 초기화

}

return answer;

def binary_search(list,item);
	lt = 0;
	rt = len(list)-1
	
	while lt <= rt:
		mid = (lt + rt) / 2
		
		if list[mid] == item:
			return mid
		if list[mid] > item:
			rt = mid - 1
		else :
			lt = mid + 1

	return None

my_list = [1,3,5,7,9]

print binary_search(my_list , 3) // 1
print binary_search(my_list, -1) // None

페이스북이 여러분들의 계정이 진짜로 존재하는지 확인하기 위해 여러분의 아이디를 찾아야합니다. 아이디가 "karlmageddon"이면, A부터 차례로 찾는것보다, 중간 어디쯤 찾기 시작하는게 나을수 있습니다.

이진 탐색을 사용하면 단계마다 절반의 숫자를 없앨 수 있다. O(logN)