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 Searching in Data Structure

$$/$$

In this module, you will learn various algorithms on two very important techniques, namely ‘searching’ and ‘sorting’.

Now, there are various algorithms designed for the implementation of each technique. You will go through most of them and see which one is the best. This analysis will be done based on what you already learnt about Big O in the Algorithm Analysis module. You will learn that using the divide and conquer technique is of immense help when it comes to improving the efficiency of algorithms.

Primarily, we will discuss the following in this module:

  • Searching

    • Linear search

    • Binary search

  • Sorting

    • Bubble sort

    • Selection sort

    • Insertion sort

    • Merge sort

    • Quick sort

 

In this session

This session will cover search techniques. You will learn two techniques, namely ‘linear search’ and ‘binary search’. So let’s begin.

 

People you will hear from in this session

Subject Matter Expert

Aishwarya Rai
Ex-Product Engineer, EdgeVerve
She worked as a software developer for Finacle at Edgeverve and helped in creating financial and e-banking software applications. She is currently working with Software Development content team at UpGrad.

 

Industry Expert

Ankit Maheshwari

Technical Lead, ImpactRun

ImpactRun is a fitness philanthropy Android application in which your every walk or run raises funds for a social cause you care about.


Presenter
Rachit Goyal

$$/$$

So, as Ankit discussed, it is very important to optimise the search technique you use, especially when dealing with big data sets. Also, Ankit talked about one of the regular tasks he used to work on at his previous organisation. He then talked about two important queries:

 

  1. To fetch the score of the user, based on the email ID

  2. To fetch the top k players on the leaderboard

 

Video Transcript

 

Hello. In this module you will learn about an extremely important and effective technique called divide and conquer. Let's first look at the roadmap you will follow. In this module, you will learn about various algorithms using two different techniques searching and sorting. You will try to optimize these algorithms using the divide and conquer technique. In the first session, you will learn about the first important technique called searching, where you will learn how to smartly search for an element in a small or big data set. This will help you save on time and go through datasets quickly. You will learn the next technique known as sorting in the next session. So let's begin your journey towards becoming an expert in the concepts of searching and sorting using the divide and conquer techniques. To become as time efficient as possible, all of you must have visited Facebook website, where you type in your email address and press Enter. Website then starts searching for the email address you entered in the database. If the email address is found, it would then try to find the match for the password that you entered with the email address. If the email address is not found, it would tell you that the email address doesn't exist in the database. Now imagine the case when your email ID is somewhere at the end of the database, which has 2 billion entries matching the email ID you entered with. Every ID in the database in such a case will take an insane amount of time. That's where the algorithm analysis you learned in the previous module will be of immense use to you. In reality, it certainly takes much less time for them to find your ID and ask you for the password. How do you think they make it possible with such a huge database? Also, how does the Google search engine find things on internet so quickly when there are billions of entries in it to search for? In this session, we will see if we have better ways algorithms for searching, which saves a lot of time and makes results available to us quickly. So first we will teach you simple but slow order and algorithms. And then we'll teach you faster algorithms that will run in order login time based on the idea of divide and conquer. Any algorithm we try, we will measure its efficiency using big O, which we learned about in the previous module. In my previous company where we used to make mobile games, I came across a situation where I had to design a real time leaderboard for our users. In that leaderboard, our users should be able to see at what ran they stand among the other players and who were the top players in the charts. In the leaderboard we had user objects, and in those user objects, we used to have email ID of the user. Email ID was the primary Identifier of the user and we used to store the score of the user. The scoring was cumulative. So every time a user scored, it used to get added to his previous score.

 

The two most important queries which we received in our system were the first one was get my score. That request had an email address and we had to fetch the score of the user based on the email address. The second query was Get top k players. That request had a parameter k and we had to fetch the top k players in the leaderboard. And both of these queries had to be as fast as possible. These sort of requests are pretty common when you are designing leaderboards. Whatever you learned in this module will be of immense help to you in solving such problems. 

 

Video Recap

 

  • This module teaches the divide and conquer technique for algorithm design optimization.

  • The module covers searching and sorting algorithms, optimizing them using divide and conquer.

  • The first session covers searching for elements in datasets using efficient algorithms to save time.

  • The next session covers sorting techniques using divide and conquer.

  • Algorithm efficiency is measured using Big O notation.

  • Real-life examples are given, such as Facebook's search for email addresses and Google's search engine.

  • The module concludes with practical applications of the techniques learned, such as designing real-time leaderboards.

 

Let’s now move to the first search technique, linear search.