สมมติว่าเรามีอาร์เรย์และเรียงลำดับจากน้อยไปมาก เราต้องกำหนดฟังก์ชันเพื่อค้นหาเป้าหมายเป็น nums หากเป้าหมายมีอยู่ ให้ส่งคืนดัชนี มิฉะนั้น ให้คืนค่า -1
ไม่ทราบขนาดอาร์เรย์ เราสามารถเข้าถึงอาร์เรย์ได้โดยใช้อินเทอร์เฟซ ArrayReader เท่านั้น มีฟังก์ชัน get เช่น ArrayReader.get(k) ซึ่งจะคืนค่าองค์ประกอบของอาร์เรย์ที่ดัชนี k
ดังนั้น หากอินพุตเป็นเหมือน array =[-1,0,3,5,9,12], target =9 ผลลัพธ์จะเป็น 4 เนื่องจากมี 9 อยู่ใน nums และดัชนีของมันคือ 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สูง :=1 ต่ำ :=0
-
ในขณะที่ได้รับ (สูง) ของผู้อ่าน <เป้าหมาย ทำ -
-
ต่ำ :=สูง
-
สูง =สูง * 2
-
-
ในขณะที่ต่ำ <=สูง ทำ -
-
กลาง :=ต่ำ + (สูง - ต่ำ) / 2
-
x :=รับ (กลาง) ของผู้อ่าน
-
ถ้า x เท่ากับเป้าหมาย −
-
คืนกลาง
-
-
ถ้า x> เป้าหมาย แล้ว −
-
สูง :=กลาง - 1
-
-
มิฉะนั้น
-
ต่ำ :=กลาง + 1
-
-
-
กลับ -1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class ArrayReader{
private:
vector<int> v;
public:
ArrayReader(vector<int> &v){
this->v = v;
}
int get(int i){
return v[i];
}
};
class Solution {
public:
int search(ArrayReader& reader, int target) {
int high = 1;
int low = 0;
while (reader.get(high) < target) {
low = high;
high <<= 1;
}
while (low <= high) {
int mid = low + (high - low) / 2;
int x = reader.get(mid);
if (x == target)
return mid;
if (x > target) {
high = mid - 1;
}
else
low = mid + 1;
}
return -1;
}
};
main(){
Solution ob;
vector<int> v = {-1,0,3,5,9,12};
ArrayReader reader(v);
cout<<(ob.search(reader, 9));
} อินพุต
{-1,0,3,5,9,12}, 9 ผลลัพธ์
4
