Java da Sıralı bir Diziye Ekleme Yeri Bulmak

Posted by dogukanhan on August 31, 2017 · 1 min read

Verilmiş sıralı bir dizi ve girilen bir değer için eğer değer dizide varsa dizideki yerini eğer dizide yoksa dizide eklenebileceği yeri döndüren algoritma.(Not: Dizide aynı elemandan sadece bir tane olduğu varsayılacaktır.)

Algoritma için  bir kaç örnek

[1,3,5,6], 5 -> 2
[1,3,5,6], 2 -> 1
[1,3,5,6], 7 -> 4
[1,3,5,6], 0 -> 0

Bu aslında binary search problemidir ve  algoritma karmaşıklılığı O(log(n)) dir.

public int searchInsert(int[] nums, int target) {
    if(nums==null)
        return -1;
    if(target>nums[nums.length-1]){
        return nums.length;
    }
 
    int i=0;
    int j=nums.length;
 
    while(i<j){
        int m=(i+j)/2;
        if(target>nums[m]){
            i=m+1;
        }else{
            j=m;
        }
    }
 
    return j;
}

Kaynak: https://www.programcreek.com/2013/01/leetcode-search-insert-position/