[Java] LeetCode 35. Search Insert Position

[Java] LeetCode 35. Search Insert Position

 

문   제 : 

정렬된 정수 배열 nums가 주어진다. 

그리고 정수 target이 주어진다.

target이 nums에 있다면, 있는 index를, 없다면 들어가야 할 index를 반환해라.

단, 시간복잡도가 O(log n) 이여야한다.

 

Constraint

{ 1 <= nums.length == 10^4 }

{ -10^4 == nums[i] <= 10^4 }

{ 1 <= n <= 100 }

{ grid[i][j] is 0 or 1 }

 

 

Example )

Input: nums = [1,3,5,6], target = 5
Output: 2

//////////////////////////////////////////////////////////

Input: nums = [1,3,5,6], target = 2
Output: 1

//////////////////////////////////////////////////////////

Input: nums = [1,3,5,6], target = 7
Output: 4

 

---

접   근 : 

배열을 반으로 갈라서 그 지점보다 큰지 작은지를 판단하면서 찾아간다.

---

해   결 : 

첫 시작점 s 는 0부터 시작한다.

첫 끝 점 e는 nums.length-1 부터 시작한다.

s와 e의 중간지점 m을 구한다.

조건에 따라 범위를 좁혀가며 target의 index를 구해준다.

 

 

---

 

결   과  :

class Solution {
    public int searchInsert(int[] nums, int target) {
        int s = 0;
        int e = nums.length-1;
        int m = s + e / 2;

        while(s <= e) {
            m = s + (e - s) / 2;
            if(target > nums[m]) s = m + 1;
            else if(target < nums[m]) e = m - 1;
            else return m;
        }
        return s;
    }
}