সূচকীয় অনুসন্ধান

এক্সপোনেনশিয়াল সার্চ ডাবলিং বা গলপিং সার্চ নামেও পরিচিত৷ এই পদ্ধতিটি অনুসন্ধান কী উপস্থাপন করতে পারে এমন পরিসর খুঁজে পেতে ব্যবহৃত হয়। যদি L এবং U তালিকার উপরের এবং নীচের সীমানা হয়, তাহলে L এবং U উভয়ই 2 এর শক্তি। শেষ বিভাগের জন্য, U হল তালিকার শেষ অবস্থান। সেই কারণে, এটি সূচকীয় হিসাবে পরিচিত।

নির্দিষ্ট পরিসর খুঁজে পাওয়ার পরে, এটি অনুসন্ধান কীটির সঠিক অবস্থান খুঁজে পেতে বাইনারি অনুসন্ধান কৌশল ব্যবহার করে।

সূচক অনুসন্ধান কৌশলের জটিলতা

সময়ের জটিলতা: O(1) সেরা ক্ষেত্রে। O(log2 i) গড় বা সবচেয়ে খারাপ ক্ষেত্রে। যেখানে আমি সেই অবস্থান যেখানে সার্চ কী উপস্থিত।
স্পেস জটিলতা: O(1)

ইনপুট এবং আউটপুট

ইনপুট:ডেটার একটি সাজানো তালিকা:10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 অনুসন্ধান কী 780 আউটপুট অবস্থান:It-এ পাওয়া গেছে অ্যালগরিদম
 
 বাইনারী অনুসন্ধান (অ্যারে, শুরু, শেষ, কী) 
 
 ইনপুট : একটি সাজানো অ্যারে, শুরু এবং শেষ অবস্থান, এবং অনুসন্ধান কী
 
 আউটপুট - চাবির অবস্থান (যদি পাওয়া যায়), অন্যথায় ভুল অবস্থান।
 শুরু হলে শুরু <=শেষ তারপর মিড :=শুরু + (শেষ - শুরু) /2 যদি অ্যারে[মিড] =কী তারপর মধ্যবর্তী অবস্থান ফেরত দেয় যদি অ্যারে[মিড]> কী তারপর বাইনারি সার্চকে কল করুন(অ্যারে, মধ্য+1, শেষ, কী) অন্যথায় যখন অ্যারে[মিড] <কী তারপর বাইনারি সার্চকে কল করুন(অ্যারে, শুরু, মধ্য-1, কী) অন্যথায় অবৈধ অবস্থান ফেরত দিনEnd
 
 সূচক অনুসন্ধান (অ্যারে, শুরু, শেষ, কী) 
 
 ইনপুট: একটি সাজানো অ্যারে, শুরু এবং শেষ অবস্থান, এবং অনুসন্ধান কী
 
 আউটপুট: চাবির অবস্থান (যদি পাওয়া যায়), অন্যথায় ভুল অবস্থান।
  শুরু করুন যদি (শেষ - শুরু) <=0 তারপরে অবৈধ অবস্থান ফেরান i :=1 যখন i <(শেষ - শুরু) করুন যদি অ্যারে[i] <কী তারপর i :=i * 2 //i শক্তি হিসাবে বৃদ্ধি করুন অফ 2 অন্য লুপ শেষ করুন কল বাইনারি সার্চ(অ্যারে, i/2, i, কী)End
 উদাহরণ
 #include namespace ব্যবহার করে std;int binarySearch(int array[], int start, int end, int key) { if(start <=end) { int mid =(start + (end - start) / 2); // তালিকার মধ্যবর্তী অবস্থান যদি (অ্যারে[মিড] ==কী) রিটার্ন মিড; if(array[mid]> key) রিটার্ন বাইনারি সার্চ(অ্যারে, স্টার্ট, মিড-1, কী); রিটার্ন বাইনারি সার্চ (অ্যারে, মধ্য+1, শেষ, কী); } return -1;}int exponentialSearch(int array[], int start, int end, int key){ if((end - start) <=0) return -1; int i =1; // হিসাবে 2^0 =1 while(i <(শেষ - শুরু)){ if(array[i] > n; int arr[n]; // আকারের একটি অ্যারে তৈরি করুন n cout <<"আইটেমগুলি লিখুন:" <> arr[i]; } cout <<"তালিকায় অনুসন্ধান করতে অনুসন্ধান কী লিখুন:"; cin>> searchKey; if((loc =exponentialSearch(arr, 0, n, searchKey))>=0) cout <<"স্থানে আইটেম পাওয়া গেছে:" < আউটপুট
 আইটেমের সংখ্যা লিখুন:20টি আইটেম লিখুন:10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 প্রবেশ করুন:অনুসন্ধান কী লিখুন:6 নম্বর তালিকাতে সন্ধান করুন:7টি তালিকার মধ্যে সন্ধান করুন