پیدا کردن محل insert در وکتور مرتب

Question

من یک وکتور کاملا مرتب دارم

حالا می خواستم بدونم اگر یک عنصر به این وکتور اضافه بشه  بدون این که ترتیب به هم بخوره  داخل چه ایندکسی قرار می گیره ؟

مثلا 

vector<int> a = {1,5,6,7,8,8,8,11,23}
//voroodi  :   4
//khorooji bayad 2 bashe

چیزی که الان نوشتم اینه :

int input=4;
vector<int> a = {1,5,6,7,8,8,8,11,23}

int pos=0;
for(auto it=a.begin();it != a.end() && input < (*it);++it){
    ++pos;
}
//pos inja 2 e

نمیخوام بصورتی خطی جست و جو کنم راه بهتری وجود داره ؟

Comments

می‌تونید به روش نصب کردن جست و جو کنید. عنصر وسط رو مقایسه کنید و طول جست و جو رو نصف کنید و عنصر وسط بخش باقی مونده رو مقایسه کنید و طول جست و جو رو نصف کنید و همین طور ادامه بدید تا به محل مناسب برسید.

---

اگر عنصر داخل لیست نباشه به محل نمیرسم .

---

فرقی نداره باشه یا نه این روش از خطی سریع تره.

---

آهان ممنون

Answer 1

از std::lower_bound که  باbinary_search  نوشته شده استفاده کن 

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
	vector<int> a = {1,5,6,7,8,8,8,11,23}
	auto it = std::lower_bound(a.begin(), a.end(),4);
	std::cout << std::distance(a.begin(), it);
}