>> [সঙ্গীত বাজাচ্ছি]
>> ডগ লয়েড: ঠিক আছে.
তাই বাইনারি অনুসন্ধান একটি হল আমরা ব্যবহার করতে পারেন অ্যালগরিদম
একটি অ্যারের ভিতরে একটি উপাদান খুঁজে পেতে.
রৈখিক অনুসন্ধান ভিন্ন, এটা প্রয়োজন একটি বিশেষ অবস্থা, পূর্বেই পূরণ করা
কিন্তু এটা এত বেশি দক্ষ হলে চলুন শর্ত যে, আসলে, পূরণ.
>> তাই ধারণা এখানে কি?
এটি বিভক্ত করা এবং বশীভূত হবে.
আমরা মাপ হ্রাস করতে চান অর্ধেক প্রতিটি সময় দ্বারা সার্চ এলাকা
লক্ষ্য সংখ্যা খুঁজে বের করার জন্য.
এই যেখানে যে অবস্থায় হয় যদিও, খেলার মধ্যে আসে.
আমরা শুধুমাত্র ক্ষমতা লিভারেজ পারেন উপাদানের দূর অর্ধেক
এমনকি এ খুঁজছেন ছাড়া তাদের অ্যারে সাজানো হয় তাহলে.
>> এটি একটি সম্পূর্ণ তালগোল যদি, আমরা শুধু হাত থেকে না পারেন
কারণ, উপাদানের অর্ধেক বাতিল আমরা খারিজ করছি কি না জানি না.
কিন্তু অ্যারে, সাজানো হয় তাহলে আমরা তা করতে পারে আমরা কারণ
যে সবকিছু জানেন আমরা বর্তমানে যেখানে বাম
কম হতে হবে মান আমরা বর্তমানে করছি.
এবং সবকিছু আমরা যেখানে ডান
মূল্য অনেক বেশী হতে হবে আমরা বর্তমানে এ খুঁজছেন.
>> সুতরাং pseudocode কি বাইনারি অনুসন্ধান জন্য পদক্ষেপ?
আমরা একই পদ্ধতি পুনরাবৃত্তি করুন অ্যারে অথবা আমরা মাধ্যমে এগিয়ে যাওয়া হিসেবে,
সাব অ্যারে, ছোট টুকরা মূল অ্যারে, মাপ 0 হয়.
মিডপয়েন্ট হিসাব বর্তমান উপ অ্যারের.
>> আপনি যা খুঁজছেন মান যদি অ্যারের যে উপাদান, বন্ধ.
তুমি কি দেখেছো এটাকে.
দারুণ.
অন্যথা, টার্গেট হয় তাহলে মাঝখানে এ কি কম,
তাই মান যদি আমরা খুঁজছেন জন্য, আমরা দেখতে চেয়ে কম
আবার এই প্রক্রিয়া পুনরাবৃত্তি, কিন্তু পরিবর্তে, শেষ বিন্দু পরিবর্তন
মূল হচ্ছে সম্পূর্ণ অ্যারে সম্পন্ন,
শুধু বাম হতে যেখানে আমরা শুধু তাকিয়ে.
>> আমরা, মাঝখানে খুব বেশী ছিল যে জানতাম বা টার্গেট, মাঝখানে ছিল কম
এবং তাই এটি বন্ধ করা আবশ্যক তা যদি এ সব অ্যারের মধ্যে বিদ্যমান
কোথাও মিডপয়েন্ট বাঁদিকে.
আর তাই আমরা অ্যারে সেট করব শুধু বাম পাঁচ
নতুন শেষ বিন্দু হিসাবে মিডপয়েন্ট.
বিপরীতভাবে, টার্গেট হয় তাহলে মাঝখানে এ কি তার চেয়ে অনেক বেশী,
আমরা সঠিক একই কাজ প্রক্রিয়া, কিন্তু এর পরিবর্তে আমরা
হতে শুরুর বিন্দু পরিবর্তন শুধু মিডপয়েন্ট ডান
আমরা শুধুমাত্র গণনা.
এবং তারপর আমরা আবার প্রক্রিয়া শুরু.
>> এর ঠিক আছে, এই দৃশ্য কল্পনা করা যাক?
সুতরাং যাচ্ছে এবং এখানে অনেক আছে, কিন্তু এখানে 15 উপাদানের একটি অ্যারে.
আর আমরা অবগত থাকার হতে যাচ্ছেন আরো অনেক কাপড় এই সময়.
তাই রৈখিক অনুসন্ধান, আমরা ছিল শুধু লক্ষ্য বিষয়ে চিন্তা করা.
কিন্তু এই সময় আমরা চাই আমরা যেখানে যত্নশীল
চেহারা শুরু, যেখানে আমরা খুঁজছি থামছি,
এবং মিডপয়েন্ট কি বর্তমান অ্যারের.
তাই এখানে আমরা বাইনারি অনুসন্ধান সঙ্গে যেতে.
আমরা প্রায় কাছাকাছি যেতে প্রস্তুত, ঠিক বলেছ?
আমি ঠিক রাখা যাচ্ছে না সূচকের একটি সেট এখানে নীচে.
এটি মূলত শুধু কি উপাদান অ্যারের আমরা যে বিষয়ে কথা বলছি.
রৈখিক অনুসন্ধান, আমরা আমরা হিসাবে কাজ সাধ্যমত, যত্ন
কতগুলি জানা প্রয়োজন আমরা উপর iterating করছি উপাদান,
কিন্তু আমরা আসলে যত্ন না কি উপাদান আমরা বর্তমানে এ খুঁজছেন.
বাইনারি অনুসন্ধান, আমরা না.
তাই যারা শুধু সেখানে একটু গাইড হিসাবে.
>> তাই আমরা ঠিক আছে, শুরু করতে পারেন?
ভাল, না পুরোপুরি.
আমি কি বলেছি মনে রেখো বাইনারি অনুসন্ধান সম্পর্কে?
আমরা একটি উপর এটি ব্যবহার করতে পারবেন না অন্য পাঁচমিশালী অ্যারে বা,
আমরা যে নিশ্চয়তা নেই নির্দিষ্ট উপাদানের বা মান নয়
ঘটনাক্রমে হচ্ছে প্রত্যাখ্যাত যখন আমরা শুধু
অ্যারে অর্ধেক উপেক্ষা করার সিদ্ধান্ত নেন.
>> তাই বাইনারি অনুসন্ধান সঙ্গে আরও এক ধাপ আপনি একটি সাজানো অ্যারের থাকতে হবে.
আর আপনি শ্রেণীবিভাজন কোনো ব্যবহার করতে পারেন আমরা স্বপ্ন করেছি আলগোরিদিম
যে অবস্থান থেকে আপনি পেতে.
তাই এখন আমরা একটি অবস্থানে যেখানে আছেন আমরা বাইনারি অনুসন্ধান সম্পাদন করতে পারবেন.
>> সুতরাং আসুন প্রক্রিয়ার পুনরাবৃত্তি দিন ধাপে ধাপে এবং রাখা
হিসাবে আমরা যেতে ঘটছে তা সম্পর্কে অবগত.
সুতরাং প্রথম আমরা নিরূপণ করা হয় না প্রয়োজন বর্তমান অ্যারের মিডপয়েন্ট.
ওয়েল, আমরা প্রথম, আমরা করছি বলবো সব, মূল্য 19 খুঁজছেন.
আমরা সংখ্যা 19 খুঁজে বের করার চেষ্টা করছেন.
এই প্রথম উপাদান অ্যারে, সূচক শূন্য এ অবস্থিত
এবং এই শেষ উপাদান অ্যারে ইনডেক্স 14 এ অবস্থিত.
আর তাই আমরা যারা শুরু এবং শেষ ডাকবো.
>> তাই আমরা মিডপয়েন্ট দ্বারা নিরূপণ 0 প্লাস 2 দ্বারা বিভক্ত 14 যোগ করার পদ্ধতি;
বেশ সহজবোধ্য মিডপয়েন্ট.
আর আমরা বলতে পারি যে, মিডপয়েন্ট এখন 7.
সুতরাং 15 আমরা যা খুঁজছেন তা হয়?
এটা না.
আমরা 19 খুঁজছেন.
কিন্তু আমরা 19 বেশী জানি যে আমরা মধ্যম এ পাওয়া কি আর.
>> তাই আমরা কি করতে পারি কি শুরুর বিন্দু পরিবর্তন
শুধু ডান হতে মিডপয়েন্ট, এবং প্রক্রিয়া আবার পুনরাবৃত্তি.
যখন আমরা যে, আমরা এখন বলতে নতুন শুরুর বিন্দু অ্যারে পাঁচ 8.
আমরা কি কার্যকরভাবে সম্পন্ন করেছি 15-এর বাঁদিক থেকে উপেক্ষিত সবকিছু.
আমরা অর্ধেক কাটানো করেছি সমস্যা, এবং এখন,
পরিবর্তে অনুসন্ধান থাকার আমাদের অ্যারের মধ্যে 15 ওভার উপাদান,
আমরা মাত্র 7 ওভার অনুসন্ধান আছে.
তাই 8 নতুন স্টার্ট হয়.
14 এখনও শেষ বিন্দু.
>> এবং এখন, আমরা আবার এই ঝালিয়ে.
আমরা নতুন মিডপয়েন্ট নিরূপণ.
8 প্লাস 14 2 11 দ্বারা বিভক্ত, 22 হয়.
এই আমরা খুঁজছেন কি?
এটা না.
আমরা যে একটি মূল্য খুঁজছেন আমরা শুধু পাওয়া তার চেয়ে কম.
সুতরাং আমরা পুনরাবৃত্তি করতে যাচ্ছেন আবার প্রক্রিয়া.
আমরা শেষ বিন্দু পরিবর্তন চলুন শুধু মিডপয়েন্ট বাঁদিকে হতে.
তাই নতুন শেষ বিন্দু 10 হয়ে যায়.
এবং এখন, যে শুধুমাত্র অংশ অ্যারে আমরা মাধ্যমে বাছাই করা আছে.
সুতরাং আমরা এখন নির্মূল 15 উপাদানের 12.
আমরা জানি 19 তাহলে যে অ্যারের মধ্যে বিদ্যমান, এটা
উপাদান মধ্যে কোথাও উপস্থিত থাকা আবশ্যক সংখ্যা 8 ও উপাদান সংখ্যা 10.
>> তাই আমরা আবার নতুন মিডপয়েন্ট নিরূপণ.
8 প্লাস 10 2 9 দ্বারা বিভক্ত, 18 হয়.
এবং এই ক্ষেত্রে, পর্যবেক্ষণ টার্গেট মধ্যম হয়.
আমরা যা খুঁজছেন ঠিক কি পাওয়া যায় নি.
আমরা বন্ধ করতে পারবেন.
আমরা সফলভাবে সম্পন্ন একটি বাইনারি অনুসন্ধান.
ঠিক আছে.
সুতরাং আমরা এই অ্যালগরিদম জানেন লক্ষ্য হয় তাহলে কাজ
কোথাও অ্যারের ভিতরে.
এই অ্যালগরিদম কাজ যদি না টার্গেট অ্যারের মধ্যে নয়?
ওয়েল, এর শুরু করা যাক আবার, এবং এই সময়,
এর উপাদান জন্য তাকান দৃশ্যত আমরা দেখতে পারেন যা 16,
অ্যারের মধ্যে যে কোন জায়গায় কোন অস্তিত্ব নেই.
>> শুরুর বিন্দু আবার 0 হয়.
শেষ বিন্দু আবার 14.
যারা প্রথম সূচকের হয় এবং সম্পূর্ণ অ্যারের শেষ উপাদান.
এবং আমরা প্রক্রিয়ার আমরা শুধু দিয়ে যাবেন মাধ্যমে গিয়েছিলাম আবার 16 খুঁজে বের করার চেষ্টা,
এমনকি দৃশ্যত যদিও, আমরা ইতিমধ্যে পারেন তা হতে যাচ্ছে না যে বলতে.
আমরা শুধু নিশ্চিত এই অ্যালগরিদম করতে চাই আসলে, এখনও কিছু উপায় কাজ করবে
এবং শুধু আমাদের ছেড়ে না অসীম লুপ আটকে.
>> তাই ধাপে প্রথম কি?
মিডপয়েন্ট হিসাব বর্তমান অ্যারের.
মিডপয়েন্ট কী বর্তমান অ্যারের?
ওয়েল, এটা ঠিক আছে, 7 এর?
2 দ্বারা বিভক্ত 14 প্লাস 0 7.
আমরা যা খুঁজছেন তা 15?
না.
এটা প্রশংসনীয় বন্ধ, কিন্তু আমরা খুঁজছেন যে চেয়ে সামান্য বড় একটি মান জন্য.
>> সুতরাং আমরা এটা যাচ্ছে যে জানি 15-এর বাঁদিক থেকে কোথাও হতে.
লক্ষ্যমাত্রার চেয়ে বেশী কি মিডপয়েন্ট আছে.
আর তাই আমরা নতুন শুরুর বিন্দু সেট শুধু মাঝখানে ডানদিকে রাখতে.
মিডপয়েন্ট তাই, বর্তমানে 7 এর নতুন স্টার্ট 8 বলা যাক.
আর আমরা কার্যকরভাবে কি করেছি আবার কাজ উপেক্ষা করা হয়
অ্যারের সমগ্র বাম অর্ধেক.
>> এখন, আমরা পুনরাবৃত্তি আরো এক সময় প্রক্রিয়া.
নতুন মিডপয়েন্ট হিসাব.
8 প্লাস 14 2 11 দ্বারা বিভক্ত, 22 হয়.
আমরা যা খুঁজছেন তা 23?
দুর্ভাগ্যক্রমে না.
আমরা একটি মান খুঁজছেন যে 23 কম.
আর তাই এই ক্ষেত্রে, আমরা চলুন শেষ বিন্দু পরিবর্তন শুধু হতে
বর্তমান মিডপয়েন্ট বাঁদিকে.
বর্তমান মিডপয়েন্ট 11, এবং তাই আমরা নতুন শেষ পয়েন্ট সেট করব
আমরা যেতে পরবর্তী সময়ের জন্য 10 এই প্রক্রিয়ার মধ্য দিয়ে.
>> আবার, আমরা আবার প্রক্রিয়ার মধ্য দিয়ে যেতে.
মিডপয়েন্ট হিসাব.
2 দ্বারা বিভক্ত 8 প্লাস 10 9.
আমরা যা খুঁজছেন তা 19?
দুর্ভাগ্যক্রমে না.
আমরা এখনও খুঁজছেন যে কম একটি সংখ্যা.
সুতরাং আমরা শেষ বিন্দু এই সময় পরিবর্তন করব শুধু মিডপয়েন্ট বাঁদিকে হতে.
মিডপয়েন্ট, বর্তমানে 9 তাই শেষ বিন্দু 8 হবে.
এবং এখন, আমরা শুধু খুঁজছেন একটি একক উপাদান অ্যারের এ.
>> এই অ্যারের মিডপয়েন্ট কী?
ওয়েল, এটা, 8 আরম্ভ 8 এ শেষ হয়, মিডপয়েন্ট 8.
যে আমরা যা খুঁজছেন তা হয়?
আমরা 17 খুঁজছেন?
না, আমরা 16 খুঁজছেন.
এটা অ্যারের মধ্যে বিদ্যমান, তাই যদি, এটা কোথাও উপস্থিত থাকা আবশ্যক
আমরা বর্তমানে যেখানে বাঁদিকে.
তাই আমরা কি করতে যাচ্ছি?
ওয়েল, আমরা শুধু হতে শেষ পয়েন্ট সেট করব বর্তমান মিডপয়েন্ট বাঁদিকে.
সুতরাং আমরা 7 শেষ বিন্দু পরিবর্তন করব.
আপনি কি শুধু দেখতে না যদিও এখানে ঘটেছে?
এখন এখানে সন্ধান.
>> এখন শুরু শেষ তার চেয়ে অনেক বেশী.
কার্যকরভাবে, দুই প্রান্ত আমাদের অ্যারের পার করেছে,
এবং শুরু বিন্দু এখন শেষ বিন্দু পরে.
ওয়েল, যে না ঠিক আছে, কোনো অনুভূতি?
সুতরাং এখন, আমরা কি বলতে পারেন আমরা হয় আকার 0 একটি সাব অ্যারে আছে.
আর একবার আমরা অর্জিত করছি এই বিন্দু, আমরা এখন যা করতে পারেন
যে উপাদান গ্যারান্টি 16 অ্যারের মধ্যে বিদ্যমান নেই,
শুরুর বিন্দু কারণ এবং শেষ পর্যন্ত পয়েন্ট অতিক্রম করেছে.
আর তাই এটি আছে না.
এখন, এই সামান্য যে লক্ষ্য শুরুর বিন্দু এবং শেষ চেয়ে ভিন্ন
একই হচ্ছে নির্দেশ.
আমরা খুঁজছি ছিল যদি 17 জন্য, এটি হবে
অ্যারে, এবং শুরুর বিন্দু হয়েছে যে সর্বশেষ পুনরাবৃত্তির এবং শেষ বিন্দু
ঐ পয়েন্ট পার আগে আমরা সেখানে 17 পেত.
তারা আমরা করতে পারেন যে ক্রস যখন এটি শুধুমাত্র উপাদান না যে গ্যারান্টি
অ্যারের মধ্যে উপস্থিত.
>> সুতরাং আসুন অনেক কম নিতে দিন রৈখিক অনুসন্ধান চেয়ে পদক্ষেপ.
লক দৃশ্যকল্প, আমরা ছিল এন উপাদানের একটি তালিকা আপ বিভক্ত
বারবার অর্ধেক, লক্ষ্য খুঁজে পেতে হয় কারণ টার্গেট উপাদান
সর্বশেষ কোথাও হতে হবে বিভাগ, অথবা এটি এ সব কোন অস্তিত্ব নেই.
খারাপ ক্ষেত্রে তাই, আমরা আছে আপনি জানেন না অ্যারে আপ বিভক্ত?
এন বার লগিন; আমরা সমস্যা কাটা আছে
সময়ের অর্ধেক একটি নির্দিষ্ট সংখ্যায়.
বার যে সংখ্যা লগ n হল.
>> শ্রেষ্ঠ কেস দৃশ্যকল্প কী?
ওয়েল, প্রথমবার আমরা মিডপয়েন্ট নিরূপণ,
আমরা যা খুঁজছেন তা খুঁজে পেতে.
সব আগের ইন বাইনারি অনুসন্ধান উদাহরণ
আমরা ছিল যদি আমরা শুধু ওভার সর্বস্বান্ত করেছি উপাদান 15 খুঁজছেন হয়েছে,
আমরা যে অবিলম্বে দেখতে পেত.
যে খুব প্রারম্ভে ছিল.
যে মিডপয়েন্ট ছিল একটি বিভক্ত এ প্রথম প্রচেষ্টা
বাইনারি অনুসন্ধান একটি বিভাগের.
>> তাই খারাপ কেস, বাইনারি অনুসন্ধান চালানো হয়
যথেষ্ট ভালো, যা লগ n, এ সবচেয়ে খারাপ ক্ষেত্রে রৈখিক অনুসন্ধান, বেশী.
সেরা ক্ষেত্রে, বাইনারি অনুসন্ধান 1 ওমেগা রান.
তাই বাইনারি অনুসন্ধান অনেক রৈখিক অনুসন্ধান চেয়ে ভাল,
কিন্তু আপনি প্রক্রিয়া মোকাবেলা করতে হবে আপনি যা করতে পারেন, প্রথমে আপনার শ্রেণীবিন্যাস বাছাই
বাইনারি অনুসন্ধান, তাদের ক্ষমতা লিভারেজ.
>> আমি ডগ লয়েড আছি.
এই সি এস 50.