[Easy] 35. Search Insert Position

Leetcode 35번 문제는 주어진 정렬된 array에서 target을 찾는 문제이다. 만약 target이 array안에 없다면, insertion point를 찾는 문제이다. Searching algorithm의 time complexity는 O(log n) 이어야 한다. Time complextiy와 array가 sorted 돼있다는 점을 고려하면 Binary Search Algoritm를 써서 풀수 있다.

 

#풀이

 public int searchInsert(int[] A, int target) {
        int low = 0, high = A.length-1;
        while(low<=high){
            int mid=low+(high-low)/2     //int mid = (low+high)/2 랑 같지만 overflow error 방지;
            if(A[mid] == target) return mid;
            else if(A[mid] > target) high = mid-1;
            else low = mid+1;
        }
        return low;
    }

Binary Search후에 만약 target를 찾지 못하면 low (binary search후 array가장 왼쪽에 있는 포인터)가 insertion포인트기 때문에 low를 return 해주면 된다.