704. Binary Search

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

Binary Search - LeetCode

난이도 : easy

문제

정렬된 nums를 입력받아 이진 검색으로 target에 해당하는 인덱스를 찾아라.

 

이진탐색 문제 풀때 유의사항

1. 주어진 배열이 정렬 여부 확인

2. 반환값이 인덱스 인덱스 여부 확인

3. 반환값이 배열의 값인지 확인

4. 배열에있는 요소가 중복으로 있을때 어느 것을 선택할 것인지.

 

코드

class Solution {
public:
    int search(vector<int>& nums, int target) {
    
        int left = 0;
        int right = nums.size() - 1;
        
        while(left <= right) {
            int mid = left + (right-left)/2;
            
            if(nums[mid] < target) {
                left = mid + 1;
            }
            else if(nums[mid] > target) {
                right = mid - 1;
            }
            else if(nums[mid] == target) {
                return mid;
            }
        }
        
        return -1;
    }
};

 

기타

mid 값을 계산할때 두번째 코드와 같이 해야 overflow 를 방지 할 수 있다. 만약 left + right 의 합이 int유효범위가 넘어간다면 오버 플로우가 발생 할 수 있다.

int mid = (left + right) / 2
(4 + 2) / 2 
= 3

int mid = left + (right-left) / 2;
2 + (4 - 2) / 2
= 3