একটি ডেটা স্ট্রাকচারে আঙুলের অনুসন্ধানকে যে কোনো সার্চ অপারেশনের একটি এক্সটেনশন হিসাবে সংজ্ঞায়িত করা হয় যা গঠন সমর্থন করে, যেখানে ডেটা স্ট্রাকচারের একটি উপাদানের রেফারেন্স (আঙুল) কোয়েরির সাথে দেওয়া হয়। যদিও একটি উপাদানের জন্য অনুসন্ধানের সময়টি প্রায়শই একটি ডেটা কাঠামোর উপাদানগুলির সংখ্যার ফাংশন হিসাবে চিহ্নিত করা হয়, আঙুল অনুসন্ধান সময়কে উপাদান এবং আঙুলের মধ্যে দূরত্বের একটি ফাংশন হিসাবে বিবেচনা করা হয়।
m উপাদানগুলির একটি সেটে, a এবং b দুটি উপাদানের মধ্যে দূরত্ব d(a, b) তাদের র্যাঙ্কের পার্থক্য। উপাদান a এবং b যদি গঠনের i-th এবং j-th বৃহত্তম উপাদান হয়, তাহলে র্যাঙ্কের পার্থক্য হল |i - j|। যদি কিছু কাঠামোতে একটি সাধারণ অনুসন্ধান সাধারণত O(f(m)) সময় ব্যয় করে, তাহলে আঙ্গুলের উপাদান b এর জন্য একটি আঙুল অনুসন্ধানের জন্য আদর্শভাবে O(f(d)) সময় ব্যয় করা উচিত। মন্তব্য করুন যে d ≤ m থেকে, এটি অনুসরণ করে যে সবচেয়ে খারাপ ক্ষেত্রে, আঙুল অনুসন্ধান সাধারণ অনুসন্ধানের মতোই খারাপ। যাইহোক, বাস্তবে এই অধঃপতিত আঙ্গুলের অনুসন্ধানগুলি সাধারণ অনুসন্ধানের চেয়ে বেশি কাজ করে। উদাহরণস্বরূপ, যদি f(n) log(n) হয়, এবং সবচেয়ে খারাপ ক্ষেত্রে আঙ্গুলের অনুসন্ধান স্বাভাবিক অনুসন্ধানের তুলনায় দ্বিগুণ তুলনা করে, এটি অনুসরণ করে যে আঙুল অনুসন্ধান যখন d> √n হয় তখন ধীর হয়। অতএব, আঙুল অনুসন্ধান শুধুমাত্র তখনই বাস্তবায়িত করা উচিত যখন কেউ যুক্তিসঙ্গতভাবে আশা করতে পারে যে লক্ষ্যটি আসলে আঙুলের কাছাকাছি হবে।
বাস্তবায়ন
কিছু জনপ্রিয় ডেটা স্ট্রাকচার প্রকৃত গঠনে অতিরিক্ত পরিবর্তন ছাড়াই আঙুল অনুসন্ধান সমর্থন করে। স্ট্রাকচারে যেখানে একটি উপাদানের অনুসন্ধান করা হয় একটি ব্যবধানকে সংকুচিত করে যার উপর a পাওয়া যায়, উপাদান b থেকে আঙুল অনুসন্ধান সাধারণত b থেকে অনুসন্ধান প্রক্রিয়াটিকে বিপরীত করে সঞ্চালিত হয় যতক্ষণ না অনুসন্ধানের ব্যবধানটি উপাদান a ধারণ করার জন্য যথেষ্ট বড় হয়। কোন পয়েন্ট সার্চ স্বাভাবিক হিসাবে এগিয়ে.
বাছাই করা লিঙ্ক তালিকা
একটি লিঙ্ক করা তালিকায়, একজন সাধারণত এক প্রান্ত থেকে অন্য প্রান্তে যাওয়ার মাধ্যমে একটি উপাদানের জন্য রৈখিক পদ্ধতিতে অনুসন্ধান করে। যদি লিঙ্ক করা তালিকাটি সাজানো হয়, এবং আমাদের b এলিমেন্ট সম্বলিত কিছু নোডের রেফারেন্স থাকে, তাহলে আমরা b এলিমেন্ট থেকে আমাদের অনুসন্ধান শুরু করে O(d) সময়ের মধ্যে একটি উপাদান খুঁজে পেতে পারি।
সর্ট করা অ্যারে
একটি সাজানো অ্যারে বি-তে, একজন সাধারণত বাইনারি অনুসন্ধানের মাধ্যমে B-এ একটি উপাদান a অনুসন্ধান করে। আঙুল অনুসন্ধান B[j] =b থেকে একতরফা অনুসন্ধান প্রয়োগ করে সঞ্চালিত হয়। যদিও বাইনারি অনুসন্ধান প্রতিটি তুলনার পরে অনুসন্ধানের স্থানকে অর্ধেক করে, একতরফা অনুসন্ধান প্রতিটি তুলনার পরে অনুসন্ধানের স্থানকে দ্বিগুণ করে। বিশেষভাবে, একতরফা অনুসন্ধানের kth পুনরাবৃত্তিতে (অনুমান করে a>b), বিবেচনাধীন ব্যবধানটি হল B[j, j+2 k-1 ]। B[j + 2 k-1 এর সাথে সাথেই সম্প্রসারণ বন্ধ হয়ে যায় ] ≥ a, যে সময়ে এই ব্যবধানটি বাইনারি উপাদান a এর জন্য অনুসন্ধান করা হয়। যদি একতরফা অনুসন্ধান একটি ব্যবধান খুঁজে পেতে k পুনরাবৃত্তি ব্যবহার করে যেটিতে a উপাদান রয়েছে, তাহলে এটি d> 2 k-2 অনুসরণ করে . এই ব্যাপ্তির বাইনারি অনুসন্ধান অন্য k পুনরাবৃত্তিও ব্যবহার করবে। অতএব, b থেকে a-এর জন্য আঙুল অনুসন্ধান O(k) =O(log d) সময়
খরচ করে.
তালিকাগুলি এড়িয়ে যান
একটি এড়িয়ে যাওয়ার তালিকায়, এই বিন্দু থেকে অনুসন্ধান চালিয়ে যাওয়ার মাধ্যমে b এলিমেন্ট ধারণকারী একটি নোড থেকে এলিমেন্ট a-এর জন্য কেউ আঙুল দিয়ে অনুসন্ধান করতে পারে। মনে রাখবেন যে যদি a
ট্রেপস
একটি ট্রিপকে একটি এলোমেলো বাইনারি অনুসন্ধান গাছ (BST) হিসাবে সংজ্ঞায়িত করা হয়। একটি ট্রিপে অনুসন্ধান করা অন্য যেকোন BST-এ একটি উপাদান অনুসন্ধান করার মতোই। তবে Treaps-এর বৈশিষ্ট্য রয়েছে যে দূরত্বের দুটি উপাদানের মধ্যে প্রত্যাশিত পথের দৈর্ঘ্যকে O(log d) হিসাবে চিহ্নিত করা হয়। এইভাবে, a এলিমেন্টের b এলিমেন্ট সম্বলিত নোড থেকে আঙ্গুল দিয়ে সার্চ করার জন্য, a এলিমেন্টের পূর্বপুরুষ না পাওয়া পর্যন্ত একজন b এলিমেন্ট থেকে গাছে আরোহণ করতে পারে, যেখানে স্বাভাবিক BST সার্চ যথারীতি চলতে থাকে। একটি নোড অন্যটির পূর্বপুরুষ কিনা তা গণনা করার সময় অ-তুচ্ছ, প্রত্যাশিত O(লগ ডি) আঙুল অনুসন্ধানের সময় প্রদান করতে এই ফর্মের প্রশ্নগুলিকে সমর্থন করার জন্য কেউ গাছটিকে বাড়িয়ে তুলতে পারে৷
দড়ি এবং গাছ
দড়ির বাস্তবায়ন (ডেটা স্ট্রাকচার) সাধারণত স্ট্রিং দেখার জন্য কর্ড পজিশন ইটারেটর ব্যবহার করে। পুনরাবৃত্তিকারীকে একটি আঙুল হিসাবে বিবেচনা করা যেতে পারে যা স্ট্রিংয়ের কিছু নির্দিষ্ট অক্ষরের দিকে নির্দেশ করে। বেশিরভাগ ভারসাম্যপূর্ণ গাছের মতো, দড়িতে গাছের একটি পাতায় ডেটা পুনরুদ্ধার করতে O(log(m)) সময় লাগে যখন শুধুমাত্র গাছের মূল দেওয়া হয়। গাছের প্রতিটি পাতা পড়ার জন্য O(m*log(m)) সময় লাগবে বলে মনে হয়। যাইহোক, সামান্য অতিরিক্ত তথ্য সংরক্ষণ করে, শুধুমাত্র O(1) সময়ে এবং একটি গাছের প্রতিটি পাতা শুধুমাত্র O(m) সময়ের মধ্যে "পরবর্তী" পাতা পড়ার জন্য পুনরাবৃত্তিকারী প্রয়োগ করা যেতে পারে।
