삽입 위치 검색 (자바 구현)

삽입 위치 검색 (자바 구현)
정렬 배열 과 목표 값 을 지정 하고 배열 에서 목표 값 을 찾 아 색인 을 되 돌려 줍 니 다.대상 값 이 배열 에 존재 하지 않 으 면 순서대로 삽 입 된 위 치 를 되 돌려 줍 니 다.너 는 배열 에 중복 요소 가 없다 고 가정 할 수 있다.

   1:
  : [1,3,5,6], 5
  : 2

   2:
  : [1,3,5,6], 2
  : 1

   3:
  : [1,3,5,6], 7
  : 4

   4:
  : [1,3,5,6], 0
  : 0

제 생각 은 간단 합 니 다. 먼저 찾 아 보고 데이터 구조의 Array List 를 통 해 찾 으 면 다음 표 시 를 되 돌려 주 는 것 입 니 다.찾 을 수 없 으 면 add 를 Array List 에 넣 고 Array List 를 정렬 하고 index Of (target) 를 사용 하여 target 의 아래 표 시 를 되 돌려 주면 됩 니 다.코드 구현:

package Day49;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @Author Zhongger
 * @Description               ，         ，      。            ，              。
 *              。
 * @Date 2020.3.23
 */
public class SearchInsertSolution {
    public static void main(String[] args) {
        int[] nums={1,3,5,6};
        int target=7;
        System.out.println(new SearchInsertSolution().searchInsert(nums, target));
    }
    public int searchInsert(int[] nums, int target) {
        if (nums==null){
            return -1;
        }
        if (nums.length<=0){
            return -1;
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            list.add(nums[i]);
            if (target==nums[i]){
                return i;
            }
        }
        list.add(target);
        Collections.sort(list);
        return list.indexOf(target);
    }
}

또 다른 방법 은 이분 검색 법 이다. 아주 간단 하 다.

 	public int searchInsert2(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }