704. Binary Search

문제 설명

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.

정수 배열 nums가 오름차순으로 정렬되어있다. 정수 target이 주어지면 nums에 target이 있는 지 탐색하여 인덱스를 리턴한다. 존재하지 않으면 -1을 리턴한다. 알고리즘은 O(logn)의 시간복잡도로 작성하시오

출력 예시

접근 방법

첫번째 시도

문제 이름이 이분탐색,,,,, 그냥 이분탐색 구현하기

소스코드

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start=0;
        int end = nums.size()-1;

        while(start <= end){
            int mid =(end+start)/2;
            if(nums[mid]>target){
                end = mid-1;
            }
            else if(nums[mid]<target){
                start = mid+1;
            }
            else return mid;
        }

        return -1;
    }
};

돌아보기

예외처리, 개수가 하나일 때 확인 제대로 하기...!!
처음에 함수 입력에 start,end가 들어가야 한다, 이분탐색은 재귀해야한다는 강박때문에 binary 함수를 새로 만들다가... 정신을 차리고 다시 풀었다. 알고리즘은 기억하되 코드를 외우지는 말자!