[704BinarySearch]

출처:

https://leetcode.com/problems/binary-search/description/

 

수도코드

function binarySearch(nums, target):
    left = 0
    right = nums.length - 1
    
    while left <= right:
        mid = left + (right - left) / 2
        
        if nums[mid] == target:
            return mid
        else if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

문제 & 해결

ⓐ 중간값 계산을 어떻게 하는가? 

left + (right - left) /2를 왜 이렇게 하지?

큰 정수를 다룰때 일반적인 중간값 계산

left + right 가 정수의 최대값을 초과할수 있기 때문에 오버플로우 방지용으로 left + (right - left) /2 이렇게 쓴다.

 

ⓑ 등호가 left랑 right 비교할때 필요한가?

left< right 조건을 사용했을시 배열에 요소 하나만 있을때 그 요소를 확인안할수 있어서 등호가 필요하다.

 

ⓒ중간 값과 타깃 비교하기

[1, 3, 5, 7, 9] 타깃 7일때

nums[mid] =5 이고 타깃이 중간값보다 크다.

왼쪽 포인터를 mid+1로 이동하면 검색범위 [7,9] 으로 변경된다. 오른쪽 절반만 계속 검사하게 된다.

타깃이 중간값보다 작으면 오른쪽 포인터를 중간값 -1으로 이동해서 왼쪽 절반을 계속 검색할수 있