Нека да разгледаме проблем на leetcode.com, предизвикателство за алгоритъм с иметоРешаване на алгоритъм за вмъкване на позиция при търсене. Тук имаме алго, което изисква от нас да проверяваме и манипулираме масив по начин, който може да бъде труден, така че нека го проверим!

Проблемът

Както е показано по-горе, нашата цел е да напишем функция, която приема сортиран масив и целева стойност и връща индекса на стойността в масива, илипо-сложната част, индексът, където стойността трябва да бъде, ако са поставени в ред. Така че, ако имаме масив от [1,3,5,6] и цел 5, връщаме индекс 2. Ако целта е 2 със същия този масив, ще върнем 1, тъй като ще я поставим между 1 и 3 на второ място в индекса.

Решението

Първо, ако масивът има целта вътре в себе си, това е лесно решение. Можем просто да поставим базов случай в началото, който проверява масива за целта и след това връща индекса, ако е вярно. Лесно-леко.

След това, тъй като работим със сортиран масив и търсим конкретно местоположение в масива, можем да използваме двоично търсене, за да подобрим ефективността си. Ще създадем две целочислени променливи, start и end (начало на инициализиране от 0, край на инициализиране като последен индекс на нашия масив),и while начало е по-малко от край, ще преминем през нашето двоично търсене. Ще създадем променлива, средна,ия дефинираме като закръглена надолу средна стойност на нашите начална и крайна стойност. След това ще проверим нашата средна стойност спрямо целевата стойност. Ако е по-голямо от, преместваме нашия край до средата 1 и започваме отначало. Ако е по-малко от, преместваме началната си стойност до средата+1 и повтаряме. Правим това, докато намерим крайното място, което трябва да бъде нашата цел. Това обаче се прекъсва, ако целта трябва да бъде поставена в самия край на масива. Имайки предвид това, ние настроихме троичен оператор, който да връща или намерения индекс, или нашата крайна начална стойност, която до този момент трябва да е с 1 по-голяма от първоначалната ни крайна стойност. Крайният ни продукт изглежда така:

Надявам се това да е било полезно! Продължавайте да практикувате тези алгоритми!