>> Rob Bowden: হাই, আমি রব নই.
কিভাবে আমরা একটি বাইনারি অনুসন্ধান চাকরী করেন?
এর বাইরে খুঁজতে দিন.
সুতরাং, এই সার্চ আমরা চলুন করে নোট recursively বাস্তবায়ন.
আপনি বাইনারি অনুসন্ধান বাস্তবায়ন হতে পারে iteratively, তাই আপনি যে না হলে,
যে পুরোপুরি সূক্ষ্ম.
>> এখন প্রথম, এর স্মরণ করা যাক কি সার্চ করার পরামিতি হতে বোঝানো হয়.
এখানে, আমরা যা int মান, দেখতে ব্যবহারকারী মান হতে অনুমিত
জন্য অনুসন্ধান.
আমরা int-মান অ্যারে, দেখতে যা আমরা করছি যা অ্যারে
মূল্য জন্য অনুসন্ধান.
এবং আমরা যা, int-এন দেখুন আমাদের অ্যারের দ্বারা.
>> এখন, প্রথম জিনিস প্রথম.
আমরা এন মধ্যে, 0 সমান দেখুন আমরা মিথ্যা ফিরে যে ক্ষেত্রে.
আমরা একটি খালি আছে যে শুধু বলছে অ্যারে, মূল্য একটি ইন পরিষ্কারভাবে নয়
খালি অ্যারের, তাই আমরা মিথ্যা ফিরে আসতে পারেন.
>> এখন, আমরা আসলে বাইনারি করে যেতে চাই বাইনারি অনুসন্ধান সন্ধানে অংশ.
সুতরাং, আমরা মধ্যম খুঁজতে চান এই অ্যারের উপাদান.
এখানে, আমরা মধ্যম বিভক্ত এন সমান বলে 2 দ্বারা, মধ্যম উপাদান থেকে
এর দৈর্ঘ্য হবে আমাদের অ্যারের 2 দ্বারা বিভক্ত.
এখন আমরা দেখতে পরীক্ষা চলুন যদি মধ্যম উপাদান আমরা এসেছি মূল্য সমান
জন্য অনুসন্ধান.
মান মধ্যম মান সমান সুতরাং, আমরা আমরা খুঁজে পাওয়া যায়, যেহেতু সত্য ফিরে আসতে পারেন
আমাদের অ্যারের মধ্যে মান.
>> কিন্তু যে সত্য ছিল না যদি, এখন আমরা recursive যা করতে হবে
বাইনারি অনুসন্ধান এর পদক্ষেপ.
আমরা করতে হয় অনুসন্ধান করা প্রয়োজন অ্যারের বা বামে
অ্যারের মাঝখানে.
মাঝখানে এ মান যদি তাই এখানে, আমরা বলতে মান কম, যে যে মান মানে
মাঝখানে তার চেয়ে অনেক বেশী ছিল অ্যারের.
তাই মান ডান হতে হবে আমরা শুধু দিকে তাকিয়ে যে উপাদান.
>> তাই এখানে, আমরা চলুন recursively অনুসন্ধান.
এবং আমরা আমরা পার করছি তাকান করব এক সেকেন্ডের মধ্যে এই করতে.
কিন্তু আমরা করতে অনুসন্ধান করতে যাচ্ছেন মধ্যম উপাদান ডান.
এবং অন্যান্য ক্ষেত্রে, এর মানে হল যে মান মাঝখানে কম ছিল
অ্যারে, এবং তাই আমরা চলুন বাঁদিকে অনুসন্ধান করতে.
এখন, বাম হতে যাচ্ছে একটু সহজ তাকান.
সুতরাং, আমরা আমরা recursively যে এখানে দেখুন যেখানে প্রথম অনুসন্ধানের আহ্বান
যুক্তি, আবার, মান আমরা ধরে খুঁজছেন.
দ্বিতীয় যুক্তি হতে যাচ্ছে আমরা উপর অনুসন্ধান করা হয় যে অ্যারে.
আর শেষ উপাদান এখন মাঝখানে হয়.
গত পরামিতি আমাদের int-হয় মনে রাখুন এন, যে আমাদের অ্যারের দ্বারা, তাই.
>> অনুসন্ধান recursive কল, আমরা করছি এখন বলছে যে দৈর্ঘ্য
অ্যারের মাঝখানে হয়.
সুতরাং, আমাদের অ্যারের আকার 20 এবং আমরা এর ছিল মাঝখানে যেহেতু, সূচক 10 এ অনুসন্ধান
20 2 দ্বারা বিভক্ত, যা আমরা করছি মানে নতুন রূপে 10 পার
আমাদের অ্যারের দ্বারা.
মনে রাখবেন যে আপনি একটি অ্যারে আছে দৈর্ঘ্য 10 হাজার, যা বৈধ মানে
উপাদানের 0 9 মাধ্যমে সূচক আছে.
তাই এই আমরা চাই ঠিক কি বাম - আমাদের আপডেট অ্যারে উল্লেখ
মধ্যম উপাদান থেকে অ্যারে.
>> সুতরাং, ডান খুঁজছেন হয় কিছুটা কঠিন.
এখন প্রথম, এর দৈর্ঘ্য বিবেচনা করা যাক ডান অ্যারের
মধ্যম উপাদান.
সুতরাং, আমাদের অ্যারের আকার n এর ছিল তারপর, নতুন অ্যারের আকার এন বিয়োগ হতে হবে
মধ্যম বিয়োগ 1.
সুতরাং, এর এন বিয়োগ মাঝখানে মনে করা যাক.
>> আবার, অ্যারের আকার 20 হাজার ছিল এবং আমরা মাঝখানে পেতে 2 দ্বারা বিভক্ত করা,
তাই মধ্যম তারপর 10, এন বিয়োগ মাঝখানে হয় আমাদের 10, তাই 10 দিতে হবে
মাঝখানে ডান উপাদান.
কিন্তু আমরা এই বিয়োগ আছে 1, আমরা চাই না, যেহেতু
মাঝখানে নিজেকে অন্তর্ভুক্ত.
তাই এন বিয়োগ মধ্যম বিয়োগ 1 আমাদের দেয় ডান উপাদানের মোট সংখ্যা
অ্যারের মধ্যে মধ্যম সূচক.
>> এখন এখানে, মনে রাখবেন যে মধ্যম পরামিতি মানের অ্যারে.
তাই এখানে, আমরা একটি ক্ষণস্থায়ী করছি আপডেট মান অ্যারে.
এই মান প্লাস মাঝখানে প্লাস 1 হয় আসলে recursively কল বলছে
অনুসন্ধান, নতুন অ্যারের মধ্যে ক্ষণস্থায়ী, যেখানে যে নতুন অ্যারে মাঝখানে শুরু হয়
প্লাস আমাদের মূল মান অ্যারের মধ্যে একজন.
>> যে জন্য একটি বিকল্প বাক্য গঠন, এখন যে আপনি হয়, পয়েন্টার দেখতে শুরু করেছি
ampersand মান মাঝখানে প্লাস 1.
সুতরাং, মধ্যম ঠিকানা দখল মূল্যবোধের প্লাস এক উপাদান.
>> এখন, আপনি আরামদায়ক না হলে আপনি, যে ভালো একটি অ্যারের পরিবর্তন
এছাড়াও ব্যবহার করে এই বাস্তবায়িত হতে পারেনি একটি recursive সাহায্যকারী ফাংশন, যেখানে
যে সাহায্যকারী ফাংশন লাগে আরো আর্গুমেন্ট.
সুতরাং পরিবর্তে শুধুমাত্র মান গ্রহণের, অ্যারে, এবং অ্যারের আকার,
সাহায্যকারী ফাংশন আরো ব্যয় হতে পারে নিম্ন সূচক সহ আর্গুমেন্ট,
আপনি অ্যারের মধ্যে যত্নশীল হবে এবং আপনি যত্ন করে উপরের সূচী
অ্যারে সম্পর্কে.
>> তাই উভয় নিম্ন সম্পর্কে অবগত থাকার সূচক এবং ঊর্ধ্ব সূচক, আপনি না
কখনও পরিবর্তন করতে হবে মূল মান অ্যারে.
আপনি ঠিক করা অব্যাহত রাখতে পারেন মান অ্যারে ব্যবহার.
কিন্তু এখানে, আমরা একটি সাহায্যকারী প্রয়োজন হবে না বিজ্ঞপ্তি যতদিন আমরা করছি হিসাবে কাজ
মূল সংশোধন করতে ইচ্ছুক মান অ্যারে.
আমরা পাস করতে ইচ্ছুক একটি আপডেট মান.
>> এখন, আমরা ধরে বাইনারি অনুসন্ধান করতে পারেন না পাঁচমিশালী যে একটি অ্যারে.
সুতরাং, আসুন এই পাবার পেতে দেওয়া.
এখন, যে ধরণের অতীতের হয় বিজ্ঞপ্তি দুই পরামিতি, যা মান int
আমরা বাছাই করছি যে অ্যারের, এবং int-n, অ্যারের দ্বারা যা যে
আমরা বাছাই করছেন.
সুতরাং, এখানে আমরা বাস্তবায়ন করতে চাই একটি বাছাই আলগোরিদিম
যে এন হে ছক হয়.
আপনি বুদ্বুদ সাজানোর, নির্বাচন চয়ন পারে সাজানোর, অথবা সন্নিবেশ সাজানোর, অথবা
এক না আছে কিছু অন্যান্য সাজানোর ক্লাসে দেখা.
কিন্তু এখানে, আমরা চলুন নির্বাচন সাজানোর ব্যবহার.
>> সুতরাং, আমরা বারবার চলুন সম্পূর্ণ অ্যারে উপর.
ভাল, এখানে আমরা আমরা iterating করছি যে দেখুন 0 থেকে n যাও বিয়োগ 1.
কেন না সব পথ এন আপ?
ভাল, আমরা ইতিমধ্যেই সাজানো করেছি প্রথম তারপর এন বিয়োগ 1 উপাদান,
ইতিমধ্যে হওয়া আবশ্যক কি শেষ উপাদান সঠিক জায়গায়, তাই ধরে বাছাই
সম্পূর্ণ অ্যারে.
>> এখন, মনে রাখবেন কিভাবে নির্বাচন সাজানোর কাজ করে.
আমরা সম্পূর্ণ অ্যারে মাধ্যমে যেতে চলুন মধ্যে সর্বনিম্ন মূল্য খুঁজছেন
অ্যারে এবং লাঠি যে শুরুতে.
তারপর আমরা সমগ্র ঝালিয়ে চলুন অ্যারে আবার দ্বিতীয় খুঁজছি
ক্ষুদ্রতম উপাদান, এবং লাঠি যে দ্বিতীয় অবস্থানে
অ্যারে, এবং তাই.
সুতরাং, যে এই কাজ হয় কি.
>> এখানে, আমরা আমরা যে দেখছি বর্তমান সর্বনিম্ন সেটিং
I-তম সূচক মূল্য.
সুতরাং প্রথম পুনরাবৃত্তির উপর, আমরা চলুন সর্বনিম্ন মান হতে বিবেচনা
আমাদের অ্যারের শুরু.
এর পরে, আমরা উপর বারবার চলুন থেকে চেক অ্যারের, বাকি
আর সেখানে কোন উপাদান ছোট দেখুন আমরা বর্তমানে যে এক
সর্বনিম্ন বিবেচনা.
>> তাই এখানে, ঞ প্লাস এক মান - যে আমরা বর্তমানে কি কম
সর্বনিম্ন বিবেচনা.
তারপর আমরা আপডেট করতে যাচ্ছেন কি আমরা ন্যূনতম মনে করি
সূচক ঞ প্লাস 1.
সুতরাং, সম্পূর্ণ অ্যারে জুড়ে যে কি, এবং এই পরে লুপ, সর্বনিম্ন জন্য
থেকে সর্বনিম্ন উপাদান হতে হবে অ্যারের মধ্যে আমি তম অবস্থানে.
>> আমরা যে আছে, আমরা অদলবদল করতে পারেন I-তম অবস্থান মধ্যে সর্বনিম্ন মূল্য
অ্যারের মধ্যে.
সুতরাং শুধু এই একটি আদর্শ ও swap হল.
আমরা একটি অস্থায়ী মান সংরক্ষণ - অ্যারের মধ্যে আমি ম মান -
অ্যারের মধ্যে আমি ম মূল্য পুরা সেখানে জন্যে যে সর্বনিম্ন মূল্য,
এবং তারপর যেখানে ফিরে সংরক্ষণ ব্যবহার করা হয়, বর্তমান সর্বনিম্ন মূল্য
অ্যারের মধ্যে আমি ম মূল্য, তাই আমরা তা হারান নি.
>> সুতরাং, যে উপর অব্যাহত পরবর্তী পুনরাবৃত্তির.
আমরা দ্বিতীয় খুঁজছেন শুরু করব সর্বনিম্ন মূল্য এবং মধ্যে যে সন্নিবেশ
দ্বিতীয় অবস্থানে.
তৃতীয় পুনরাবৃত্তির অন, আমরা জন্য সন্ধান করব তৃতীয় সর্বনিম্ন মূল্য এবং সন্নিবেশ
যে তৃতীয় অবস্থান মধ্যে, এবং তাই আমরা একটি সাজানো অ্যারের আছে যতক্ষণ নেভিগেশন.
আমার নাম রব, এবং এই নির্বাচন সাজানোর ছিল.