COURSES
MBAData Science & AnalyticsDoctorate Software & Tech AI | ML MarketingManagement
Professional Certificate Programme in HR Management and AnalyticsPost Graduate Certificate in Product ManagementExecutive Post Graduate Program in Healthcare ManagementExecutive PG Programme in Human Resource ManagementMBA in International Finance (integrated with ACCA, UK)Global Master Certificate in Integrated Supply Chain ManagementAdvanced General Management ProgramManagement EssentialsLeadership and Management in New Age BusinessProduct Management Online Certificate ProgramStrategic Human Resources Leadership Cornell Certificate ProgramHuman Resources Management Certificate Program for Indian ExecutivesGlobal Professional Certificate in Effective Leadership and ManagementCSM® Certification TrainingCSPO® Certification TrainingLeading SAFe® 5.1 Training (SAFe® Agilist Certification)SAFe® 5.1 POPM CertificationSAFe® 5.1 Scrum Master Certification (SSM)Implementing SAFe® 5.1 with SPC CertificationSAFe® 5 Release Train Engineer (RTE) CertificationPMP® Certification TrainingPRINCE2® Foundation and Practitioner Certification
Law
Job Linked
Bootcamps
Study Abroad
Master of Business Administration (90 ECTS)Master of Business Administration (60 ECTS)Master in Computer Science (120 ECTS)Master in International Management (120 ECTS)Bachelor of Business Administration (180 ECTS)B.Sc. Computer Science (180 ECTS)MS in Data AnalyticsMS in Project ManagementMS in Information TechnologyMasters Degree in Data Analytics and VisualizationMasters Degree in Artificial IntelligenceMBS in Entrepreneurship and MarketingMSc in Data AnalyticsMS in Data AnalyticsMaster of Science in AccountancyMS in Computer ScienceMaster of Science in Business AnalyticsMaster of Business Administration MS in Data ScienceMS in Information TechnologyMaster of Business AdministrationMS in Applied Data ScienceMaster of Business AdministrationMS in Data AnalyticsM.Sc. Data Science (60 ECTS)Master of Business AdministrationMS in Information Technology and Administrative Management MS in Computer Science Master of Business Administration MBA General Management-90 ECTSMSc International Business ManagementMS Data Science MBA Business Technologies MBA Leading Business Transformation Master of Business Administration MSc Business Intelligence and Data ScienceMS Data Analytics MS in Management Information SystemsMSc International Business and ManagementMS Engineering ManagementMS in Machine Learning EngineeringMS in Engineering ManagementMSc Data EngineeringMSc Artificial Intelligence EngineeringMPS in InformaticsMPS in Applied Machine IntelligenceMS in Project ManagementMPS in AnalyticsMS in Project ManagementMS in Organizational LeadershipMPS in Analytics - NEU CanadaMBA with specializationMPS in Informatics - NEU Canada Master in Business AdministrationMS in Digital Marketing and MediaMS in Project ManagementMaster in Logistics and Supply Chain ManagementMSc Sustainable Tourism and Event ManagementMSc in Circular Economy and Sustainable InnovationMSc in Impact Finance and Fintech ManagementMS Computer ScienceMS in Applied StatisticsMS in Computer Information SystemsMBA in Technology, Innovation and EntrepreneurshipMSc Data Science with Work PlacementMSc Global Business Management with Work Placement MBA with Work PlacementMS in Robotics and Autonomous SystemsMS in Civil EngineeringMS in Internet of ThingsMSc International Logistics and Supply Chain ManagementMBA- Business InformaticsMSc International ManagementMS Computer Science with AIML ConcentrationMBA in Strategic Data Driven ManagementMaster of Business AdministrationMSc Digital MarketingMBA Business and MarketingMaster of Business AdministrationMSc Digital MarketingMSc in Sustainable Luxury and Creative IndustriesMSc in Sustainable Global Supply Chain ManagementMSc in International Corporate FinanceMSc Digital Business Analytics MSc in International HospitalityMSc Luxury and Innovation ManagementMaster of Business Administration-International Business ManagementMS in Computer EngineeringMS in Industrial and Systems EngineeringMSc International Business ManagementMaster in ManagementMSc MarketingMSc Business ManagementMSc Global Supply Chain ManagementMS in Information Systems and Technology with Business Intelligence and Analytics ConcentrationMSc Corporate FinanceMSc Data Analytics for BusinessMaster of Business AdministrationMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSBachelors in International Management
For College Students

Introduction to Binary Search Algorithm

$$/$$

The concept of divide and conquer that you learnt about in the previous video leads to another search algorithm called Binary Search. If you understood the phonebook example well, you already know what binary search is. Let’s now explore it further. 

$$/$$

So, for binary search, you need a sorted array. You can not apply binary search on an array thats not sorted. You start at the middle index and compare the element you’re searching for with the element at the middle index. If the element at this index does not match the element you’re searching for, you check if it is greater or lesser than the element at the index. If it is greater than the element at the middle index, you discard everything to the left and move to the right. You then find the middle of this array that’s to the right, compare the required element with its middle, and keep doing this till you find the required element. In the next video, you will get an intuition to why Binary Search takes significantly less number of steps than Linear Search.

 

Video Transcript

 

Now suppose you are given a sorted array like this. So in a sorted array, all the elements are arranged in an increasing order. Now, suppose I say that I have to find an element x here and say x is equal to 23. So the technique which you learned till now was linear search. So what near search used to do? It used to compare each and every element of the array with the element which I want to find. But can we utilize the fact that this array A is sorted in the increasing order? Can we perhaps decrease the number of steps which I would require to find my element x equals to 23? Think about it and write your answers in the question that follow. So the algorithm which utilizes the fact that I have a sorted array here is known as the binary search. Now, as you know that if I would have done a linear search on this, it would have taken me 123456 number of steps to arrive at my element 23. Now we'll see how I can reduce these six number of steps using binary search. Let us move step by step. So in the first step, what I'll do is that I'll find the middle element of this array. Now, since this array consists of ten elements, so my fifth element is going to be my middle one, which is 16 in this case. Now, if you think about it carefully, you would know that since all the elements are arranged in an increasing order, so the elements which lie towards the left of 16 will definitely be less than 23 because 16 itself is less than 23. So in my next step, what I can do is that I can safely ignore this left portion of my array. In the next step, my array would then be reduced to all the elements which lie towards the right of 16. Let me write my new array here then.

 

So this denotes the array in my second step. Now, if I have to find 23 here, I'll again repeat the same procedure and find the middle element of this array. Since this consists of five elements, my middle element would be 56. On comparing 56 with 23, I find that since 56 is greater than 23, so if 23 were existing inside this array, it would definitely lie towards the left of 56. So what I'll do, I will ignore the right hand portion of this array and consider only the left portion. Now, in my next step I would see that my array has been reduced to this.

 

Here again, I would find the middle element of this array which will be this element. On comparing it with 23 I would find that since x a which was 23 equals this element. So I have successfully found out my element number 23 here. And how many steps did it take? It took me exactly three number of steps to arrive that 23 exists here in this array, at this index. Compare it with the six number of steps you took to find in linear search. Here in binary search, we took half number of steps, which was three. So binary search is definitely a very good way of finding a certain element given in a sorted array.

 

Video Recap

 

  • How to find an element in a sorted array using binary search algorithm

  • Linear search involves comparing each element with the given element and is time-consuming

  • Binary search utilizes the fact that the array is sorted in increasing order to reduce the number of steps required to find the element

  • Binary search involves finding the middle element of the array and comparing it with the given element

  • Depending on the comparison result, either the left or the right portion of the array is ignored in the next step

  • This process is repeated until the element is found

  • Binary search algorithm takes fewer steps compared to linear search, making it an efficient way to find an element in a sorted array.

 

$$/$$

Let's now move onto the next segment where we discuss the pseudocode for Binary Search algorithm.