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.
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.
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.
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.
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.
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.
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.
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.
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 –
85 Online Courses | 67 Hands-on Projects | 660+ Hours | Verifiable Certificate of Completion
4.8
View Course
Related Courses
