EDUCBA

EDUCBA

MENUMENU
  • Explore
    • Lifetime Membership
    • All in One Bundles
    • Fresh Entries
    • Finance
    • Data Science
    • Programming and Dev
    • Excel
    • Marketing
    • HR
    • PDP
    • VFX and Design
    • Project Management
    • Exam Prep
    • All Courses
  • Blog
  • Enterprise
  • Free Courses
  • Log in
  • Sign up
Home Data Science Data Science Tutorials Data Structures Tutorial Binary Search in Data Structure

Binary Search in Data Structure

Updated March 10, 2023

Binary Search in Data Structure

Definition of Binary Search in Data Structure

Binary search is an advanced search in data structure and it is used to find the specified value from the array. Basically, binary search works on the sorted array list that means before the search for any value of the item, we must ensure that the given array list is sorted. Binary search works on the divide and conquer approach, in which we first divide the given list into two parts and compare these two parts with the middle of the list. If any value matches or is found, then it returns the location of that value otherwise search depends on the result.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Syntax

BINARY_SEARCH (LIST, LEFT_VALUE, RIGHT_VALUE, VALUE)

Step 1: First we need to initialize the variable such as SET START = LEFT_VALUE

END = RIGHT_VALUE, LOC = -1

Step 2: Repeat steps 3 and 4 until START is less than or equal to END i.e START<=END.

Step 3: In step 3 we need to find the mid-value by using the following formula.

SET MID_PT = (START + END)/2

Step 4: IF LIST [MID_PT] = VALUE

SET LOC = MID_PT
PRINT LOC
Go to step 6
ELSE IF LIST [MID_PT] >VALUE
SET END = MID_PT – 1
ELSE
SET START = MID_PT + 1
[HERE END IF LOOP]

Step 5: IF LOC = -1

Then print values not present in list or array.

End of IF loop

Step 6: Exit.

Explanation: In the above syntax that we also called the algorithm, here we use different steps to implement the binary search. In the first step, we need to initialize the variable such as LIST, LEFT_VALUE, RIGHT_VALUE and VALUE. In the second step, we compare two parts of the list that mean the left part is less than or equal to the right part then we repeat some steps that are mentioned in the above syntax. After that, we need to find the midpoint and compare the left value and right value as shown in the above syntax.

How does Binary Search Work in Data Structure?

Now let’s see how binary search works in a data structure as follows.

For a binary search, we must need a sorted array or list to implement a binary search. We will become familiar with the process of binary search with a pictorial model. Coming up next is our arranged exhibit and allowed us to accept that we need to look through the area of significant worth 35 utilizing the binary search.

Binary Search in Data Structure -1.1

In figure show a sorted array or list with the position of value that we call the location, which we need to implement binary search because binary search works as linear search.

Now find the middle of this by using the following formula as follows.

MID_PT = START + END /2

Here, START is 0 and END is 9

So, 0 + 9 = 4.5

So we take an integer value that is 4 and this is the MID_PTof the list as shown below figure as follows.

Binary Search in Data Structure -1.2

Now we need to compare the searchvalue with location 4. See here at 4th location we got 30 and our search value is 35 that mean value does not match. If the search value is less than MID_PT then we search value on the left side and if the value is greater than MID_PT then we search value on the right side because we know the list is sorted. So in this example, we need to search the value on the right side as shown below figure.

Binary Search in Data Structure -1.3

Now change the value of START and MID_PT as follows.

START = MID_PT + 1

MID_PT = START + END /2

Then we got a newMID_PT that is 7, now compare the search value with MID_PT, see here search value is less than MID_PT.

Note here search value is 35 less than MID_PT which means we need to follow the same process that is found MID_PT and check if the value is less or greater. To conclude our search value 35 we got at the 5th location as shown in the below figure as follows.

Binary Search in Data Structure -1.4

Examples of Binary Search in Data Structure

Now see an example of binary search by using a python programming language as follows. Normally we can implement binary search by using different programming languages but here we try to implement by using python programming as follows.

Example #1

Code:

defbinary_Search(list, start, end, value):
if end >= start:
mid_pt = int((start + end) / 2)
if list[mid_pt] == value:
return mid_pt + 1
elif list[mid_pt] < value:
return binary_Search(list, mid_pt + 1, end, value)
else:
return binary_Search(list, start, mid_pt - 1, value)
return -1
list = [10, 15, 17, 25, 30, 35, 37, 40, 45, 50];
value = int(input("Enter the which value you want to search: "))
loc = -1;
loc = binary_Search(list, 0, 9, value);
if loc != -1:
print(" search value is match at location %d" % (loc))
else:
print("search value not found")

Explanation: In the above example we use python programming language, in this example, we follow the same steps that are mentioned in the above point. End output of the above code we illustrated by using the following screenshot as follows.

Output  -1.5

In the above screenshot, we try to search value 35 if the value is found in a static list then it shows the message search value is found at the location as shown in the above screenshot. If I need to search 5 value but this value is not present in the list then it shows message search value not found as shown in the below screenshot as follows.

Output  -1.6

Example #2

Similarly, we can implement binary search by using c programming language as follows.

Code:

#include<stdio.h>
intbinarySearch(int[], int, int, int);
void main()
{
intlist[10] = {10, 15, 17, 25, 30, 35, 37, 40, 45, 50};
int value, loc=-1;
printf("Enter the value which you want to search ");
scanf("%d",&value);
loc = binarySearch(list, 0, 9, value);
if(loc != -1)
{
printf("Search value found at location %d",loc);
}
else
{
printf("Search value not found");
}
}
intbinarySearch(int l[], int start, int end, int value)
{
intmid_pt;
if(end >= start)
{
mid_pt = (start + end)/2;
if(l[mid_pt] == value)
{
return mid_pt+1;
}
else if(l[mid_pt] < value)
{
return binarySearch(l,mid_pt+1,end,value);
}
else
{
return binarySearch(l,start,mid_pt-1,value);
}
}
return -1;
}

Explanation: By using the above c code we try to implement binary search in the data structure, so in this way wecan use any programming language to implement binary search. End output of the above code we illustrated by using the following screenshot as follows.

Output -1.7

Conclusion

We hope from this article you learn the Binary Search in Data structure. From the above article, we have learned the basic syntax of Binary Search and we also see different examples of Binary Search. From this article, we learned how and when we use the Binary Search in Data structure.

Recommended Articles

This is a guide to Binary Search in Data Structure. Here we also discuss the introduction and syntax of binary search in a data structure along with different examples and its code implementation. You may also have a look at the following articles to learn more –

  1. Searching in Data Structure
  2. Pattern Searching
  3. NumPy searchsorted
  4. MySQL Full Text Search
ADVERTISEMENT
All in One Excel VBA Bundle
500+ Hours of HD Videos
15 Learning Paths
120+ Courses
Verifiable Certificate of Completion
Lifetime Access
ADVERTISEMENT
Financial Analyst Masters Training Program
2000+ Hours of HD Videos
43 Learning Paths
550+ Courses
Verifiable Certificate of Completion
Lifetime Access
ADVERTISEMENT
All in One Data Science Bundle
2000+ Hour of HD Videos
80 Learning Paths
400+ Courses
Verifiable Certificate of Completion
Lifetime Access
ADVERTISEMENT
All in One Software Development Bundle
5000+ Hours of HD Videos
149 Learning Paths
1050+ Courses
Verifiable Certificate of Completion
Lifetime Access
Primary Sidebar
Footer
Follow us!
  • EDUCBA FacebookEDUCBA TwitterEDUCBA LinkedINEDUCBA Instagram
  • EDUCBA YoutubeEDUCBA CourseraEDUCBA Udemy
APPS
EDUCBA Android AppEDUCBA iOS App
Blog
  • Blog
  • Free Tutorials
  • About us
  • Contact us
  • Log in
  • Blog as Guest
Courses
  • Enterprise Solutions
  • Free Courses
  • Explore Programs
  • All Courses
  • All in One Bundles
  • Sign up
Email
  • [email protected]

ISO 10004:2018 & ISO 9001:2015 Certified

© 2023 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

🚀 Cyber Monday Reloaded Price Drop! All in One Universal Bundle (3700+ Courses) @ 🎁 90% OFF - Ends in ENROLL NOW