বাইনারি সার্চ ইমপ্লিমেন্টেশনে একটি সাধারণ সমস্যা

আমরা জানি বাইনারি সার্চ অ্যালগরিদম লিনিয়ার সার্চের চেয়ে ভালো। এই অ্যালগরিদম O(log n) টাইম নেয়। কিন্তু অধিকাংশ কেসে ইমপ্লিমেন্ট করা কোডে কিছু সমস্যা থাকে। একটি বাইনারি সার্চ ফাংশন বিবেচনা করুন −

উদাহরণ

int binarySearch(int array[], int start, int end, int key){ if(start <= end){ int mid = (start + end) /2); //mid location of the list if(array[mid] == key) return mid; if(array[mid] > key) return binarySearch(array, start, mid-1, key); return binarySearch(array, mid+1, end, key); } return -1; }

এই অ্যালগরিদম ঠিক কাজ করবে যতক্ষণ না start এবং end বড় সংখ্যায় পৌঁছায়। যদি (start + end) 2³² − 1-এর মান অতিক্রম করে, তবে এটি র‍্যাপ আপ হয়ে একটি নেগেটিভ নম্বর রিটার্ন করতে পারে। এবং যেহেতু নেগেটিভ নম্বর অ্যারে ইনডেক্স হিসেবে সাপোর্টেড নয়, তাই সমস্যা হতে পারে।

এই সমস্যা ওপর কাবু পেতে কিছু ভিন্ন পদ্ধতি রয়েছে।

পদ্ধতি ১

int mid = start + ((end - start) / 2)

দ্বিতীয় পদ্ধতি শুধু জাভায় কাজ করবে কারণ C বা C++-তে >>> অপারেটর নেই।

পদ্ধতি ২ (শুধু জাভা)

int mid = (start + end) >>> 1

যেহেতু >>> C বা C++-তে সাপোর্টেড নয়, তাই আমরা নিচের পদ্ধতি ব্যবহার করতে পারি।

পদ্ধতি ৩

int mid = ((unsigned int) low + (unsigned int) high) >> 1