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

What is the Code for Binary Search? User Guide

$$/$$

Now that you have learnt what binary search is, let’s look at the Java implementation of the algorithm. But before we move onto the Java implementation, let's first discuss the pseudocode of the algorithm.

$$/$$

Video Transcript

 

So now we'll take a look at a simple pseudocode for binary search and try to relate it with the example we already discussed. So if you look here carefully, you would see that my function binary will take in two inputs which is a and t which denotes the array and the element t, which I want to find whether it exists in the array or no. So here I have defined some variables. Variable n denotes the length of the array. My variable start denotes the starting index of the current array which I'll be considering. I'll be initializing it with zero here and another variable end, which will be initialized to the last index of the array which is n minus one. So let me relate it to the example here. So in my case, my starting index would be this one and my ending index would be this one. Now, let us move and see this step here. What I am doing is that I'm finding the middle element of the array by calculating the mid index here. Mid denotes the middle index of the entire array which will be equal

 

to start plus end by two. Now, in my case, my mid index would be this one, which will be the fifth index. Now, in the next step, what I am doing is that I have three if else conditions and I'm comparing my middle value with the value which I want to find, which is my target value. So in my case, I would see and compare my target value with the mid value. In this case, my mid value equals to 16 and my target value equals to 23. So in the first if loop, I would check whether t equals to equals to amid, that is whether 23 is equal to equal to 16. Since this is not true, I move on to my next if condition. My next if condition says to check if amid is less than t here t is equal to x, which is my target value which is 23, and amid is 16. Since t is greater than amid. I would go into this if condition and update my start index to mid plus one. So this is what is happening actually in step number two. Let us revisit. My starting index was here, ending index was here and mid index was here. I was

 

comparing my target value with the value at the middle index. I found out that my target value is greater than the mid value. So what I'll do in this step, I'm updating my start pointer to mid plus one here. Mid was here. So what I'll do in my next step, my start value will come here, which is mid plus one. This you can clearly see in this step, which is step number two. Now, the array which I'll be considering is this one. This will denote the start index and this would denote my ending index. Again, notice that the start index was updated to mid plus one. And so that is why the array which I'll be considering in this step would be this one. I'll be repeating the same procedure again. I would again calculate my mid index for this particular array here. My start index is here, and ending index is here. So my mid index would be start plus end by two. Since there are five elements here, my mid index would be this one. Now, again, I'll be going into three FL conditions and check which one

 

of them holds. Again, my target value is 23 and my amid value, which is the middle value, is 56. Certainly they both are not equal. I would go into my next if loop and see whether amid is less than t here. Amid is 56, which is the middle value, and t is 23, since 56 is greater than 23. This if condition would not hold. So I would go into my next else if condition, which says that in case my amid value comes out to be greater than my target value, which is represented here, in the last if else condition, I would update my end pointer to mid minus one. Now, you would have seen my ending pointer was here. Now, what the algorithm tells me to do is that I should update my ending pointer to mid minus one, which is I should bring my ending pointer here since this is mid. So mid minus one would be here. So this is what is happening in the next step. In the next step, my s pointer remains constant, whereas my e pointer, my ending pointer, has shifted and come here on 38. So in this step, I would

 

be left with two elements. In this case, my start element would be this one and my ending index would be this one. I would then repeat the procedure again and find the mid index. In this case, my mid index would come out to be the same as the start index, which is this one. Now, I go into the first if condition and see if my target value equals to equals to amid. Since my mid was this and amid equals to 23, it matches with the target value of 23. So this if condition has been successful. So on the success of a condition, what I do I return mid. That is, I return the index of this particular element since it matches with our target value. So this is how I keep on checking in each step how my mid index value compares with the target value I want to find. And based on that, I update either my start pointer or I update my end pointer. Or if those two values match, then I return the index of the matched element.

 

Video Recap

 

Binary search algorithm helps to find if a specific element exists in a sorted array.

  • The function 'binary' takes two inputs: array 'a' and target element 't'.

  • The variables n, start, and end are defined where n denotes array length, start denotes starting index, and end denotes ending index of the array.

  • The middle element is found by calculating the mid index as  (start + end) / 2.

  • There are three if-else conditions to compare the target value with the middle value.

  • If the target value is greater than the middle value, then the start pointer is updated to mid + 1.

  • If the target value is less than the middle value, then the end pointer is updated to mid - 1.

  • This process is repeated until the target element is found or the search space is exhausted.

  • If the target element is found, then the index of the element is returned.

  • Binary search works efficiently with a sorted array.

  •  

Learn how binary search works with this simple pseudocode and example. The function 'binary' takes two inputs - the array and the element to find. The algorithm compares the target value with the middle value and updates the start or end pointers accordingly. Repeat until the target element is found or the search space is exhausted. This efficient algorithm returns the index of the matched element. Use binary search with a sorted array to find elements quickly.

 

We know that all is not explained till now. There has not been any discussion on why the condition start<= end is being used in the pseudocode. You shall be provided with an explanation for the same in the next video.

$$/$$

Great! If you have understood the pseudocode well, the Java implementation discussed in the video below shall be a cake-walk for you. You can download the Java file given below for Binary Search Code.

$$/$$

Though in the video and at many other places in this course, Aishwarya has used (start + end)/2 to calculate the value of the middle index, and it works fine in most of the cases as well, we still recommend you to use either of the following:

start + ((end - start) / 2);

(The reason for the same can be found here.)

or 

start + (end - start)/2

(The reason for the same can be found here.)

 

Great! You now know how to write a Java code for the binary search algorithm. So, let’s move to the next video, where Rachit will find the jack of spades in the same set of 11 cards. Let’s see how many steps he takes using binary search.

$$/$$

So, it took Rachit four steps using binary search, while it took 11 steps using linear search. This clearly illustrates the fact that binary search is much more efficient than linear search.