[LeetCode][JAVA] 35. Search Insert Position

Contents

 

타겟의 숫자가 있는 nums 배열의 번호를 찾아라

 

문제 설명

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

 

주어진 정렬된 정수의 배열과 타겟의 값이 있다. 만약 타겟의 값이 인덱스에서 발견된다면 반환하고, 그렇지 않다면 순서상 인덱스에 있을 곳을 반환하라.

---

 

제한사항

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

---

 

입출력 예시

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

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

---

 

설계 / 아이디어

---

 

문제 풀이

class Solution {
    public int searchInsert(int[] nums, int target) {    
        int start = 0;
        int end = nums.length - 1;
        
        while (start <= end) {
            int mid = (start + end) / 2;
            
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] > target) {
                end = mid - 1;
            }
            else {
                start = mid + 1;
            }
        }
        return start;
    }
}