![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674102543232-Binary%20Search%20In%20Data%20Structure.jpg\")
<\/p>\n<\/p>\n
In this blog, we will talk about binary search in data structure. Binary Search is one of the most curious topics of data structures as it decreases the time complexity for searching an element in the array from O(N) to O(logN). Not only this, we will also discuss the advantages, drawbacks, applications, and when to use binary search in data structure. Let\u2019s walk slowly and discuss what is binary search in data structure and how to implement binary search in data structure in different languages.<\/p>\n
Binary Search is a searching technique used in a sorted array by repeatedly dividing the search interval in half. Utilizing the knowledge that the array is sorted, the binary search focuses on decreasing the time complexity to O(LogN).
\nWith this method, an array’s middle is always searched for the element.<\/p>\n
Note:<\/strong> A sorted list of items is the only type of list on which a binary search can be used. We must first sort the elements if they are not already sorted.<\/p>\n There are two techniques to implement binary search algorithms, which are explained below.<\/p>\n The divide and conquer strategy is used in the recursive approach. Let x = 4 serve as the search element.<\/p>\n Return mid if x == mid. Otherwise, compare the searchable element with m.<\/p>\n<\/li>\n If x > mid, evaluate x against the middle element of the elements to its right. Setting low to low = mid + 1 achieves this.<\/p>\n<\/li>\n Else, make a comparison of x with the element in the middle of the elements to the left of mid. Setting high to high = mid – 1 accomplishes this.<\/p>\n<\/li>\n<\/ol>\n Here, we will see the pseudocode for binary search in data structure in both iterative as well as recursive methods.<\/p>\n Code Implementation of Iterative Method For Binary Search In C language<\/strong><\/p>\n\t\t\t\t\t\tDry Run For Binary Search In C Language<\/h3>\n
\n
\nThe general procedures for both approaches are covered here.<\/p>\n\n
\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674102543343-Binary%20Search%20In%20Data%20Structure1.png\")
<\/li>\n<\/ol>\n\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674102543343-Binary%20Search%20In%20Data%20Structure2.png\")
<\/p>\n\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674102543353-Binary%20Search%20In%20Data%20Structure3.png\")
<\/p>\n\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674102543353-Binary%20Search%20In%20Data%20Structure4.png\")
<\/p>\n\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674102543353-Binary%20Search%20In%20Data%20Structure5.png\")
<\/p>\n\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674102543353-Binary%20Search%20In%20Data%20Structure6.png\")
<\/p>\nPseudocode for Binary Search Algorithm<\/h2>\n
Iteration Method<\/h3>\n
do until the pointers low and high meet each other.\n mid = (low + high)\/2\n if (x == arr[mid])\n return mid\n else if (x > arr[mid]) \/\/ x is on the right side\n low = mid + 1\n else \/\/ x is on the left side\n high = mid - 1<\/code><\/pre>\nRecursive Method<\/h3>\n
binarySearch(arr, x, low, high)\n if low > high\n return False \n else\n mid = (low + high) \/ 2 \n if x == arr[mid]\n return mid\n else if x > arr[mid] \/\/ x is on the right side\n return binarySearch(arr, x, mid + 1, high)\n else \/\/ x is on the right side\n return binarySearch(arr, x, low, mid - 1)<\/code><\/pre>\n