title

7.2 What is Binary Search | Binary Search Algorithm with example | Data Structures Tutorials

description

CORRECTION: In the while loop the condition should be l less than equal to r.
Discussed Binary Search Algorithm-Divide and Conquer Method, Analysis of Binary Search Algorithm, Iterative Method, Time Complexity of Binary Search
Linear search:
https://youtu.be/C46QfTjVCNU
DSA Full Course: https: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8LU
******************************************
See Complete Playlists:
C Programming Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31a8UcMN9-35ghv8qyFWD9_S
C++ Programming: https://www.youtube.com/playlist?list=PLdo5W4Nhv31YU5Wx1dopka58teWP9aCee
Python Full Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bZSiqiOL5ta39vSnBxpOPT
Printing Pattern in C: https://www.youtube.com/playlist?list=PLdo5W4Nhv31Yu1igxTE2x0aeShbKtVcCy
DAA Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31ZTn2P9vF02bkb3SC8uiUUn
Placement Series: https://www.youtube.com/playlist?list=PLdo5W4Nhv31YvlDpJhvOYbM9Ap8UypgEy
Dynamic Programming: https://www.youtube.com/playlist?list=PLdo5W4Nhv31aBrJE1WS4MR9LRfbmZrAQu
Operating Systems: //www.youtube.com/playlist?list=PLdo5W4Nhv31a5ucW_S1K3-x6ztBRD-PNa
DBMS: https://www.youtube.com/playlist?list=PLdo5W4Nhv31b33kF46f9aFjoJPOkdlsRc
*******************************************
Connect & Contact Me:
Facebook: https://www.facebook.com/Jennys-Lectures-CSIT-Netjrf-316814368950701/
Quora: https://www.quora.com/profile/Jayanti-Khatri-Lamba
Instagram: https://www.instagram.com/jayantikhatrilamba/
#binarysearch #linearsearch #datastructures

detail

{'title': '7.2 What is Binary Search | Binary Search Algorithm with example | Data Structures Tutorials', 'heatmap': [{'end': 159.666, 'start': 138.779, 'weight': 0.745}, {'end': 301.113, 'start': 251.344, 'weight': 0.85}, {'end': 389.599, 'start': 310.543, 'weight': 0.764}, {'end': 975.278, 'start': 928.796, 'weight': 0.973}, {'end': 1100.2, 'start': 1068.343, 'weight': 0.735}], 'summary': 'Covers the working principle of binary search, binary search algorithm, step-by-step implementation, time complexity, and efficiency comparison with linear search, providing examples and emphasizing the divide and conquer approach, with o(log n) worst case and o(1) best case time complexity.', 'chapters': [{'end': 74.131, 'segs': [{'end': 74.131, 'src': 'embed', 'start': 24.383, 'weight': 0, 'content': [{'end': 27.926, 'text': 'but the data in this array is what sorted.', 'start': 24.383, 'duration': 3.543}, {'end': 34.767, 'text': 'right, if the data is not sorted, then you cannot apply binary search on that array.', 'start': 27.926, 'duration': 6.841}, {'end': 37.507, 'text': 'you have to first sort the array.', 'start': 34.767, 'duration': 2.74}, {'end': 40.928, 'text': 'then you can apply binary search for searching.', 'start': 37.507, 'duration': 3.421}, {'end': 46.489, 'text': 'so here the precondition for this binary search is the array should be sorted.', 'start': 40.928, 'duration': 5.561}, {'end': 49.209, 'text': 'that is not a case in linear search.', 'start': 46.489, 'duration': 2.72}, {'end': 54.89, 'text': 'that linear search works fine on the sorted array as well as on unsorted array.', 'start': 49.209, 'duration': 5.681}, {'end': 59.42, 'text': 'now we will see how this binary search algorithm will work.', 'start': 54.89, 'duration': 4.53}, {'end': 60.601, 'text': 'fine, see.', 'start': 59.42, 'duration': 1.181}, {'end': 62.662, 'text': 'so now we are going to search for the data.', 'start': 60.601, 'duration': 2.061}, {'end': 63.983, 'text': 'or you can say key 59.', 'start': 62.662, 'duration': 1.321}, {'end': 66.826, 'text': 'is this 59 present in this area or not?', 'start': 63.983, 'duration': 2.843}, {'end': 70.889, 'text': 'and if present, your code should return where this 59 is present.', 'start': 66.826, 'duration': 4.063}, {'end': 74.131, 'text': 'the index at which this 59 is present, see.', 'start': 70.889, 'duration': 3.242}], 'summary': 'Binary search requires sorted array, works for finding 59 in an array, and returns its index.', 'duration': 49.748, 'max_score': 24.383, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA24383.jpg'}], 'start': 0.049, 'title': 'Binary search working principle', 'summary': 'Explains the working principle of binary search using an example, emphasizing the need to sort the array beforehand, and comparing it with linear search.', 'chapters': [{'end': 74.131, 'start': 0.049, 'title': 'Binary search working principle', 'summary': 'Explains the working principle of binary search using an example and highlights the prerequisite of sorting the array before applying binary search, contrasting it with linear search.', 'duration': 74.082, 'highlights': ['Binary search requires the array to be sorted as a prerequisite, contrasting with linear search which works on both sorted and unsorted arrays.', 'The example demonstrates the process of applying binary search to find a specific data point, such as the presence of the key 59 and returning its index.']}], 'duration': 74.082, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA49.jpg', 'highlights': ['The example demonstrates the process of applying binary search to find a specific data point, such as the presence of the key 59 and returning its index.', 'Binary search requires the array to be sorted as a prerequisite, contrasting with linear search which works on both sorted and unsorted arrays.']}, {'end': 268.863, 'segs': [{'end': 127.713, 'src': 'embed', 'start': 74.131, 'weight': 0, 'content': [{'end': 78.995, 'text': 'one more important point about this binary search algorithm is what it is divide and conquer technique.', 'start': 74.131, 'duration': 4.864}, {'end': 82.138, 'text': 'it means it is going to divide the array into two halves.', 'start': 78.995, 'duration': 3.143}, {'end': 83.459, 'text': 'recursively. divide the array.', 'start': 82.138, 'duration': 1.321}, {'end': 89.068, 'text': 'now how recursively it will divide the array into subarrays, we are going to see.', 'start': 83.999, 'duration': 5.069}, {'end': 93.436, 'text': 'see, in this case we are going to find out the middle element of the array.', 'start': 89.068, 'duration': 4.368}, {'end': 97.146, 'text': 'fine, so we are going to take two variables.', 'start': 93.436, 'duration': 3.71}, {'end': 102.789, 'text': 'first is here left variable and we are going to point left.', 'start': 97.146, 'duration': 5.643}, {'end': 105.13, 'text': 'here means l value is zero.', 'start': 102.789, 'duration': 2.341}, {'end': 111.534, 'text': 'next variable is right and the value of this right is nine, or you can say n minus one.', 'start': 105.13, 'duration': 6.404}, {'end': 119.598, 'text': 'so in this algorithm we are going to find out the mid position of the array from where we are going to divide the array into two halves.', 'start': 111.534, 'duration': 8.064}, {'end': 127.713, 'text': 'fine, see, First of all, the left is 0 and the right is 9 in this case.', 'start': 119.598, 'duration': 8.115}], 'summary': 'Binary search algorithm uses divide and conquer technique to recursively divide the array into subarrays, with initial left and right values of 0 and 9.', 'duration': 53.582, 'max_score': 74.131, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA74131.jpg'}, {'end': 165.067, 'src': 'heatmap', 'start': 138.779, 'weight': 0.745, 'content': [{'end': 143.161, 'text': '0 plus 9 divide by 2 is what? 4.5 floor value is 4.', 'start': 138.779, 'duration': 4.382}, {'end': 145.302, 'text': 'So mid is what? 4.', 'start': 143.161, 'duration': 2.141}, {'end': 150.143, 'text': 'So at index 4 we are having? mid now.', 'start': 145.302, 'duration': 4.841}, {'end': 151.984, 'text': 'now, here three cases can be there.', 'start': 150.143, 'duration': 1.841}, {'end': 159.666, 'text': 'first case is the data you want to find out is equal to the data at the mid position fine.', 'start': 151.984, 'duration': 7.682}, {'end': 165.067, 'text': 'second case is the data is less than the data which is at mid position?', 'start': 159.666, 'duration': 5.401}], 'summary': 'Using floor value, identify data position in array.', 'duration': 26.288, 'max_score': 138.779, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA138779.jpg'}, {'end': 184.386, 'src': 'embed', 'start': 159.666, 'weight': 4, 'content': [{'end': 165.067, 'text': 'second case is the data is less than the data which is at mid position?', 'start': 159.666, 'duration': 5.401}, {'end': 167.807, 'text': 'or third case is the data you want to find out?', 'start': 165.067, 'duration': 2.74}, {'end': 173.729, 'text': 'the key you want to find out find out is greater than the data which is at mid position.', 'start': 167.807, 'duration': 5.922}, {'end': 177.664, 'text': 'so so these are three cases.', 'start': 173.729, 'duration': 3.935}, {'end': 178.964, 'text': 'find data is equal to this.', 'start': 177.664, 'duration': 1.3}, {'end': 180.885, 'text': 'mid data is less than this.', 'start': 178.964, 'duration': 1.921}, {'end': 182.946, 'text': 'a of mid and data is greater than a of mid.', 'start': 180.885, 'duration': 2.061}, {'end': 184.386, 'text': 'three cases can be there.', 'start': 182.946, 'duration': 1.44}], 'summary': 'Three cases for finding data: less than, equal to, or greater than mid position.', 'duration': 24.72, 'max_score': 159.666, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA159666.jpg'}, {'end': 249.923, 'src': 'embed', 'start': 216.439, 'weight': 2, 'content': [{'end': 219.542, 'text': 'now we can say this 59 is present to the right of this mid.', 'start': 216.439, 'duration': 3.103}, {'end': 221.804, 'text': 'now, how you can say this?', 'start': 219.542, 'duration': 2.262}, {'end': 224.727, 'text': 'because we know that the array is sorted.', 'start': 221.804, 'duration': 2.923}, {'end': 234.013, 'text': 'And if array is sorted, then all the data which is greater than 25 Must be present to the right of this 25.', 'start': 225.347, 'duration': 8.666}, {'end': 239.957, 'text': 'Now we are going to search only in this array.', 'start': 234.013, 'duration': 5.944}, {'end': 242.558, 'text': 'We have divided our search space.', 'start': 239.957, 'duration': 2.601}, {'end': 249.923, 'text': 'First, our search space is this one After first comparison, we have divided it into half.', 'start': 242.558, 'duration': 7.365}], 'summary': 'Array is sorted, 59 is right of 25.', 'duration': 33.484, 'max_score': 216.439, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA216439.jpg'}], 'start': 74.131, 'title': 'Binary search and searching algorithm', 'summary': 'Discusses the binary search algorithm and searching techniques in a sorted array, emphasizing the divide and conquer approach and the process of narrowing down the search space. it demonstrates the recursive division of the array and provides an example of finding the data 59 in the given array.', 'chapters': [{'end': 159.666, 'start': 74.131, 'title': 'Binary search algorithm', 'summary': 'Explains the divide and conquer technique of the binary search algorithm, demonstrating how the array is divided into two halves recursively and how the mid position is found to perform the division.', 'duration': 85.535, 'highlights': ['The binary search algorithm employs the divide and conquer technique, dividing the array into two halves recursively to find the mid position, which is crucial for the search process.', 'The algorithm sets the left variable to 0 and the right variable to 9, then calculates the mid position using the formula (L + R) / 2 and taking the floor value, resulting in the mid position being 4 in this case.', 'The chapter explains the three possible cases when finding the mid position: when the data to be found is equal to the data at the mid position.']}, {'end': 268.863, 'start': 159.666, 'title': 'Searching algorithm explanation', 'summary': 'Explains the process of searching for a specific data in a sorted array using a divide and conquer approach, emphasizing on the three cases and the process of narrowing down the search space based on comparisons, with a focus on the example of finding the data 59 in the given array.', 'duration': 109.197, 'highlights': ['The process of narrowing down the search space based on comparisons is explained, emphasizing on dividing the array into two parts and focusing on the example of finding the data 59 in the given array.', 'Explanation of the three cases involved in the search process, including the scenarios where the data is equal to the mid position, less than the mid position, and greater than the mid position in the array.', 'Emphasizing on the significance of the array being sorted, indicating that all data greater than 25 must be present to the right of 25, thus narrowing down the search space and focusing the search in a specific subarray.']}], 'duration': 194.732, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA74131.jpg', 'highlights': ['The binary search algorithm employs the divide and conquer technique, dividing the array into two halves recursively to find the mid position.', 'The algorithm sets the left variable to 0 and the right variable to 9, then calculates the mid position using the formula (L + R) / 2 and taking the floor value, resulting in the mid position being 4 in this case.', 'The process of narrowing down the search space based on comparisons is explained, emphasizing on dividing the array into two parts and focusing on the example of finding the data 59 in the given array.', 'Emphasizing on the significance of the array being sorted, indicating that all data greater than 25 must be present to the right of 25, thus narrowing down the search space and focusing the search in a specific subarray.', 'The chapter explains the three possible cases when finding the mid position: when the data to be found is equal to the data at the mid position.', 'Explanation of the three cases involved in the search process, including the scenarios where the data is equal to the mid position, less than the mid position, and greater than the mid position in the array.']}, {'end': 543.53, 'segs': [{'end': 389.599, 'src': 'heatmap', 'start': 310.543, 'weight': 0.764, 'content': [{'end': 311.363, 'text': 'now what you can say.', 'start': 310.543, 'duration': 0.82}, {'end': 320.488, 'text': 'data is present to the left of 63 here, only because data is less than 63 and array is sorted so now.', 'start': 311.363, 'duration': 9.125}, {'end': 324.09, 'text': 'so now, if data is present to the left of mid, to the left of mid,', 'start': 320.488, 'duration': 3.602}, {'end': 332.275, 'text': 'in that case what you will do left would be as it is 5 and this right would be moved towards this side.', 'start': 324.09, 'duration': 8.185}, {'end': 334.576, 'text': 'so now right becomes mid minus 1.', 'start': 332.275, 'duration': 2.301}, {'end': 336.657, 'text': 'now here we have right.', 'start': 334.576, 'duration': 2.081}, {'end': 346.288, 'text': 'because now we are going to work only in this space, here only, we again divided the array into two parts.', 'start': 338.544, 'duration': 7.744}, {'end': 350.15, 'text': 'that is why i was saying we recursively divide the array into two parts.', 'start': 346.288, 'duration': 3.862}, {'end': 352.551, 'text': 'fine, until you find the element.', 'start': 350.15, 'duration': 2.401}, {'end': 355.943, 'text': 'so now r is what 6, mid minus 1.', 'start': 352.551, 'duration': 3.392}, {'end': 357.074, 'text': '7 minus 1 is 6.', 'start': 355.943, 'duration': 1.131}, {'end': 359.835, 'text': 'now again, find out the mid 5 plus 6 is 11 by 2.', 'start': 357.074, 'duration': 2.761}, {'end': 360.876, 'text': 'that is 5.5.', 'start': 359.835, 'duration': 1.041}, {'end': 362.557, 'text': 'floor value is 5.', 'start': 360.876, 'duration': 1.681}, {'end': 366.162, 'text': 'so mid is now here 5..', 'start': 362.557, 'duration': 3.605}, {'end': 369.246, 'text': 'L is also 5 and mid is also 5 now.', 'start': 366.162, 'duration': 3.084}, {'end': 373.853, 'text': 'Right? Now check.', 'start': 371.209, 'duration': 2.644}, {'end': 376.376, 'text': 'Is 59 same as A of mid? No.', 'start': 373.953, 'duration': 2.423}, {'end': 378.979, 'text': '59 is greater than A of mid.', 'start': 377.578, 'duration': 1.401}, {'end': 389.599, 'text': 'it means 59 is present to the right of mid, to the right area of this mid right, and if this is present, the data is present to the right of the mid.', 'start': 379.853, 'duration': 9.746}], 'summary': 'Searching for data in a sorted array using binary search algorithm.', 'duration': 79.056, 'max_score': 310.543, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA310543.jpg'}, {'end': 543.53, 'src': 'embed', 'start': 515.091, 'weight': 0, 'content': [{'end': 525.218, 'text': 'And if array is sorted, then all the data which is greater than 25 Must be present to the right of this 25.', 'start': 515.091, 'duration': 10.127}, {'end': 529.701, 'text': 'Now we are going to search only in this array.', 'start': 525.218, 'duration': 4.483}, {'end': 532.322, 'text': 'We have divided our search space.', 'start': 529.701, 'duration': 2.621}, {'end': 539.667, 'text': 'First, our search space is this one After first comparison, we have divided it into half.', 'start': 532.322, 'duration': 7.345}, {'end': 541.088, 'text': 'Now this is our search space.', 'start': 539.667, 'duration': 1.421}, {'end': 543.53, 'text': 'We are going to search from here to here now.', 'start': 541.088, 'duration': 2.442}], 'summary': 'Search in sorted array, 25+ data to right. divided search space.', 'duration': 28.439, 'max_score': 515.091, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA515091.jpg'}], 'start': 268.863, 'title': 'Binary search algorithm', 'summary': "Explains the binary search algorithm and its step-by-step implementation using relevant quantifiable data to find a specific element in a sorted array, detailing the process of dividing the search space in half and iteratively narrowing it down based on the comparison of the target value with the middle element's value.", 'chapters': [{'end': 366.162, 'start': 268.863, 'title': 'Binary search algorithm', 'summary': 'Explains the binary search algorithm and its step-by-step implementation, using relevant quantifiable data, to find a specific element in a sorted array.', 'duration': 97.299, 'highlights': ['The algorithm involves identifying the middle index of the array, which is used to compare with the target element, enabling the reduction of the search space by half. The process is repeated until the target element is found, demonstrating the efficiency of the binary search algorithm.', 'The process entails the consistent division of the array into two parts, showcasing the logarithmic time complexity of O(log n) in finding the target element, improving the efficiency of the search operation.', "The algorithm's key feature is its ability to efficiently locate the target element, as evidenced by the reduction in the search space from 9 elements to 1 element in just a few steps, demonstrating its superior performance compared to linear search algorithms."]}, {'end': 543.53, 'start': 366.162, 'title': 'Binary search algorithm', 'summary': "Explains the binary search algorithm, detailing the process of finding a specific element in a sorted array by dividing the search space in half and iteratively narrowing it down based on the comparison of the target value with the middle element's value.", 'duration': 177.368, 'highlights': ['The algorithm involves repeatedly dividing the search space in half based on comparisons, leading to a time complexity of O(log n).', 'The process includes identifying whether the target value is greater or less than the middle element to determine the new search space and effectively narrow down the potential locations of the target element.', 'The stopping conditions of the algorithm are when the target element is found at the middle index, or when the search space has been fully explored without finding the target element.']}], 'duration': 274.667, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA268863.jpg', 'highlights': ['The process entails the consistent division of the array into two parts, showcasing the logarithmic time complexity of O(log n) in finding the target element, improving the efficiency of the search operation.', 'The algorithm involves identifying the middle index of the array, which is used to compare with the target element, enabling the reduction of the search space by half. The process is repeated until the target element is found, demonstrating the efficiency of the binary search algorithm.', 'The algorithm involves repeatedly dividing the search space in half based on comparisons, leading to a time complexity of O(log n).', "The algorithm's key feature is its ability to efficiently locate the target element, as evidenced by the reduction in the search space from 9 elements to 1 element in just a few steps, demonstrating its superior performance compared to linear search algorithms.", 'The process includes identifying whether the target value is greater or less than the middle element to determine the new search space and effectively narrow down the potential locations of the target element.', 'The stopping conditions of the algorithm are when the target element is found at the middle index, or when the search space has been fully explored without finding the target element.']}, {'end': 758.238, 'segs': [{'end': 664.349, 'src': 'embed', 'start': 609.549, 'weight': 0, 'content': [{'end': 615.812, 'text': 'so now, if data is present to the left of mid, to the left of mid, in that case what you will do left would be,', 'start': 609.549, 'duration': 6.263}, {'end': 621.334, 'text': 'as it is 5 and this right would be moved towards this side.', 'start': 615.812, 'duration': 5.522}, {'end': 623.635, 'text': 'so now right becomes mid minus 1.', 'start': 621.334, 'duration': 2.301}, {'end': 625.716, 'text': 'now here we have right.', 'start': 623.635, 'duration': 2.081}, {'end': 635.347, 'text': 'because now we are going to work only in this space, here only we again divided the array into two parts.', 'start': 627.605, 'duration': 7.742}, {'end': 639.209, 'text': 'that is why i was saying we recursively divide the array into two parts.', 'start': 635.347, 'duration': 3.862}, {'end': 641.609, 'text': 'fine, until you find the element.', 'start': 639.209, 'duration': 2.4}, {'end': 644.21, 'text': 'so now r is what 6.', 'start': 641.609, 'duration': 2.601}, {'end': 645, 'text': 'mid minus 1.', 'start': 644.21, 'duration': 0.79}, {'end': 646.131, 'text': '7 minus 1 is 6.', 'start': 645, 'duration': 1.131}, {'end': 647.291, 'text': 'now again, find out the mid.', 'start': 646.131, 'duration': 1.16}, {'end': 648.891, 'text': '5 plus 6 is 11 by 2.', 'start': 647.291, 'duration': 1.6}, {'end': 649.932, 'text': 'that is 5.5.', 'start': 648.891, 'duration': 1.041}, {'end': 651.612, 'text': 'floor value is 5.', 'start': 649.932, 'duration': 1.68}, {'end': 653.453, 'text': 'so mid is now here.', 'start': 651.612, 'duration': 1.841}, {'end': 658.123, 'text': 'L is also 5 and mid is also 5.', 'start': 654.64, 'duration': 3.483}, {'end': 663.368, 'text': 'now, right Now check is 59, same as A.', 'start': 658.123, 'duration': 5.245}, {'end': 664.349, 'text': 'No 59 is greater than A.', 'start': 663.368, 'duration': 0.981}], 'summary': 'The transcript explains a process of recursively dividing an array to find an element using specific calculations.', 'duration': 54.8, 'max_score': 609.549, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA609549.jpg'}, {'end': 758.238, 'src': 'embed', 'start': 732.188, 'weight': 1, 'content': [{'end': 736.158, 'text': 'so now here you are going to stop and you are going to return mid.', 'start': 732.188, 'duration': 3.97}, {'end': 743.263, 'text': 'return mid means you are going to return the index 6 where the data is present.', 'start': 738.018, 'duration': 5.245}, {'end': 746.486, 'text': 'fine, so this is the one stopping condition now.', 'start': 743.263, 'duration': 3.223}, {'end': 756.316, 'text': 'second case is if data is not present in the array, in that case, when you are going to stop your searching algorithm, let us take that case,', 'start': 746.486, 'duration': 9.83}, {'end': 757.617, 'text': 'only that case also.', 'start': 756.316, 'duration': 1.301}, {'end': 758.238, 'text': 'now let us take.', 'start': 757.617, 'duration': 0.621}], 'summary': 'Algorithm stops at index 6 when data is present in array.', 'duration': 26.05, 'max_score': 732.188, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA732188.jpg'}], 'start': 544.636, 'title': 'Binary search algorithm', 'summary': 'Explains the binary search algorithm, its process of dividing the array, finding the mid value, comparing data with the mid value, and demonstrates a step-by-step process of finding an element in an array, leading to the index of the target element.', 'chapters': [{'end': 664.349, 'start': 544.636, 'title': 'Searching algorithm explanation', 'summary': 'Explains the binary search algorithm, where an array is divided into two parts until the element is found, with the key points being the process of dividing the array, finding the mid value, and comparing the data with the mid value.', 'duration': 119.713, 'highlights': ['The array is divided into two parts until the element is found, with the left variable being moved to the right and the right variable being moved to the left.', 'The process involves finding the mid value by calculating the average of the left and right indices and comparing the data with the mid value to determine the next step.', 'The importance of recursively dividing the array into two parts until the element is found is emphasized.']}, {'end': 758.238, 'start': 668.914, 'title': 'Binary search algorithm', 'summary': 'Explains the binary search algorithm and its stopping conditions, demonstrating a step-by-step process of finding an element in an array using left and right pointers while analyzing the midpoint, ultimately leading to the index of the target element.', 'duration': 89.324, 'highlights': ['The algorithm explains the process of binary search and its stopping conditions, demonstrating the step-by-step approach of finding an element in an array, with a specific example showing the calculation of the midpoint and the comparison with the target element, resulting in the index of the element.', 'The chapter provides a detailed explanation of the binary search algorithm, including the handling of stopping conditions such as finding the element in the array and the scenario where the element is not present, offering a thorough understanding of the search process.', 'The demonstration includes the handling of specific cases within the binary search algorithm, showcasing the process of identifying the presence of an element in an array and the subsequent stopping conditions, enhancing comprehension of the search methodology.']}], 'duration': 213.602, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA544636.jpg', 'highlights': ['The importance of recursively dividing the array into two parts until the element is found is emphasized.', 'The chapter provides a detailed explanation of the binary search algorithm, including the handling of stopping conditions such as finding the element in the array and the scenario where the element is not present, offering a thorough understanding of the search process.', 'The demonstration includes the handling of specific cases within the binary search algorithm, showcasing the process of identifying the presence of an element in an array and the subsequent stopping conditions, enhancing comprehension of the search methodology.', 'The array is divided into two parts until the element is found, with the left variable being moved to the right and the right variable being moved to the left.', 'The process involves finding the mid value by calculating the average of the left and right indices and comparing the data with the mid value to determine the next step.', 'The algorithm explains the process of binary search and its stopping conditions, demonstrating the step-by-step approach of finding an element in an array, with a specific example showing the calculation of the midpoint and the comparison with the target element, resulting in the index of the element.']}, {'end': 1087.456, 'segs': [{'end': 990.387, 'src': 'heatmap', 'start': 928.796, 'weight': 0, 'content': [{'end': 935.541, 'text': 'in that case, if data is not present right now, i am going to write a piece of code for this binary search.', 'start': 928.796, 'duration': 6.745}, {'end': 938.443, 'text': 'see, i am going to create a function, binary search.', 'start': 935.541, 'duration': 2.902}, {'end': 948.942, 'text': 'In this I am going to pass array a total number of elements in the array and the data you want to search.', 'start': 942.119, 'duration': 6.823}, {'end': 951.023, 'text': 'So now, first of all, what we have done.', 'start': 949.622, 'duration': 1.401}, {'end': 956.906, 'text': 'we have taken l is equal to 0 and r is equal to n, minus 1.', 'start': 951.023, 'duration': 5.883}, {'end': 963.989, 'text': 'n is 10, so r was 9, fine, and after that we have calculated what mid.', 'start': 956.906, 'duration': 7.083}, {'end': 971.075, 'text': 'So now mid is equal to l plus r divide by 2.', 'start': 964.549, 'duration': 6.526}, {'end': 975.278, 'text': 'right. after calculating mid we are checked three conditions right.', 'start': 971.075, 'duration': 4.203}, {'end': 976.919, 'text': 'three cases can be there.', 'start': 975.278, 'duration': 1.641}, {'end': 984.143, 'text': 'so we have checked if data is equal to is equal to a of mid.', 'start': 976.919, 'duration': 7.224}, {'end': 990.387, 'text': 'if this is true, then you will do what return mid?', 'start': 984.143, 'duration': 6.244}], 'summary': 'Creating a binary search function to find data in an array of 10 elements.', 'duration': 39.364, 'max_score': 928.796, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA928796.jpg'}, {'end': 1087.456, 'src': 'embed', 'start': 1025.794, 'weight': 1, 'content': [{'end': 1029.656, 'text': 'and the third case, as data is present to the right of the smith.', 'start': 1025.794, 'duration': 3.862}, {'end': 1031.238, 'text': 'in that case you will move left.', 'start': 1029.656, 'duration': 1.582}, {'end': 1034.079, 'text': 'left becomes mid plus 1.', 'start': 1031.238, 'duration': 2.841}, {'end': 1040.344, 'text': 'else l becomes mid plus 1 right.', 'start': 1034.079, 'duration': 6.265}, {'end': 1045.488, 'text': 'and you are going to repeat these steps till left.', 'start': 1040.344, 'duration': 5.144}, {'end': 1048.833, 'text': 'l is less than r.', 'start': 1046.352, 'duration': 2.481}, {'end': 1053.035, 'text': 'once l becomes greater than r, it means data not found right.', 'start': 1048.833, 'duration': 4.202}, {'end': 1054.876, 'text': 'so you are going to repeat these steps.', 'start': 1053.035, 'duration': 1.841}, {'end': 1068.343, 'text': 'so you are going to write down these steps in a loop, that is, while l is less than r till then these steps should be repeated.', 'start': 1054.876, 'duration': 13.467}, {'end': 1073.005, 'text': 'if l is not less than r, it means obviously l would be greater than r.', 'start': 1068.343, 'duration': 4.662}, {'end': 1083.447, 'text': 'so here you can return what minus 1, minus 1 means data is not present right and you can close this function.', 'start': 1073.005, 'duration': 10.442}, {'end': 1087.456, 'text': 'So this is how the binary search is going to work.', 'start': 1084.775, 'duration': 2.681}], 'summary': 'Binary search finds data in a sorted array by iterating left and right pointers until the data is found or determined to be not present.', 'duration': 61.662, 'max_score': 1025.794, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA1025794.jpg'}], 'start': 758.238, 'title': 'Binary search algorithm', 'summary': 'Explains the steps of the binary search algorithm, iteratively dividing the search range to find the position of an element in an array, with middle element comparison and conditional moves, concluding with a function definition.', 'chapters': [{'end': 1087.456, 'start': 758.238, 'title': 'Binary search algorithm', 'summary': 'Explains the steps of the binary search algorithm, where it iteratively divides the search range to find the position of an element in an array, with the middle element comparison and conditional moves, and concludes with a function definition.', 'duration': 329.218, 'highlights': ['The algorithm iteratively divides the search range to find the position of an element in an array, with the middle element comparison and conditional moves.', 'The function definition includes the initialization of pointers, calculation of the middle element, and the three conditions for comparing the data with the middle element.', 'The condition for data not found is addressed with the return of -1, and the iterative steps are enclosed in a while loop until the left pointer becomes greater than the right pointer.']}], 'duration': 329.218, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA758238.jpg', 'highlights': ['The function definition includes the initialization of pointers, calculation of the middle element, and the three conditions for comparing the data with the middle element.', 'The algorithm iteratively divides the search range to find the position of an element in an array, with the middle element comparison and conditional moves.', 'The condition for data not found is addressed with the return of -1, and the iterative steps are enclosed in a while loop until the left pointer becomes greater than the right pointer.']}, {'end': 1409.3, 'segs': [{'end': 1391.396, 'src': 'embed', 'start': 1333.649, 'weight': 0, 'content': [{'end': 1334.73, 'text': 'So the time complexity.', 'start': 1333.649, 'duration': 1.081}, {'end': 1340.354, 'text': 'how many times this loop has been executed? Log n times.', 'start': 1334.73, 'duration': 5.624}, {'end': 1346.026, 'text': 'right here also, you can see log n times.', 'start': 1342.082, 'duration': 3.944}, {'end': 1357.218, 'text': 'so if such kind of behavior occurs, if loop is going to doubles or loop is going to half, in that case always the time complexity is order of log n.', 'start': 1346.026, 'duration': 11.192}, {'end': 1363.324, 'text': 'so in binary search also, we are going to divide the space by half, then again half, then again half.', 'start': 1357.218, 'duration': 6.106}, {'end': 1365.466, 'text': 'so this is the case.', 'start': 1364.105, 'duration': 1.361}, {'end': 1375.67, 'text': 'so the time complexity would be log n here, and this log n is far better than the order of n.', 'start': 1365.466, 'duration': 10.204}, {'end': 1377.771, 'text': 'that is the time complexity of linear search.', 'start': 1375.67, 'duration': 2.101}, {'end': 1385.674, 'text': 'that is why i was saying that this is the most popular searching algorithm, because of this time complexity only.', 'start': 1377.771, 'duration': 7.903}, {'end': 1388.615, 'text': 'in the worst case, the time complexity is order of log n.', 'start': 1385.674, 'duration': 2.941}, {'end': 1391.396, 'text': 'in average case also the time complexity is order of log n.', 'start': 1388.615, 'duration': 2.781}], 'summary': 'Binary search has time complexity of o(log n), far better than linear search (o(n)).', 'duration': 57.747, 'max_score': 1333.649, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA1333649.jpg'}], 'start': 1087.936, 'title': 'Binary search time complexity', 'summary': 'Discusses the time complexity of binary search, highlighting o(log n) in the worst case and o(1) in the best case. it also compares the time complexity with linear search, demonstrating the efficiency of binary search.', 'chapters': [{'end': 1141.96, 'start': 1087.936, 'title': 'Time complexity of binary search', 'summary': 'Discusses the time complexity of the binary search algorithm, highlighting that in the worst case, the time complexity is o(log n) due to continuously halving the search space, while in the best case, it is o(1) due to a direct match.', 'duration': 54.024, 'highlights': ['In the worst case, the time complexity of the binary search algorithm is O(log n) as the search space is continuously halved, resulting in a logarithmic time complexity.', 'In the best case scenario, when the desired element is found in the first comparison, the time complexity of the binary search algorithm is O(1), indicating a constant time complexity.']}, {'end': 1409.3, 'start': 1141.96, 'title': 'Time complexity and binary search', 'summary': 'Explains time complexity using for loops and calculates the time complexity for two different cases, showing how the time complexity of binary search is log n, which is far better than the time complexity of linear search.', 'duration': 267.34, 'highlights': ['The time complexity of binary search is log n, which is far better than the order of n time complexity of linear search.', 'The for loop in binary search doubles or halves in each iteration, leading to a time complexity of log n, making it the most popular searching algorithm.']}], 'duration': 321.364, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V_T5NuccwRA/pics/V_T5NuccwRA1087936.jpg', 'highlights': ['In the worst case, the time complexity of the binary search algorithm is O(log n) as the search space is continuously halved, resulting in a logarithmic time complexity.', 'The time complexity of binary search is log n, which is far better than the order of n time complexity of linear search.', 'In the best case scenario, when the desired element is found in the first comparison, the time complexity of the binary search algorithm is O(1), indicating a constant time complexity.', 'The for loop in binary search doubles or halves in each iteration, leading to a time complexity of log n, making it the most popular searching algorithm.']}], 'highlights': ['Binary search requires the array to be sorted as a prerequisite, contrasting with linear search which works on both sorted and unsorted arrays.', 'The algorithm involves repeatedly dividing the search space in half based on comparisons, leading to a time complexity of O(log n).', 'The process entails the consistent division of the array into two parts, showcasing the logarithmic time complexity of O(log n) in finding the target element, improving the efficiency of the search operation.', 'In the best case scenario, when the desired element is found in the first comparison, the time complexity of the binary search algorithm is O(1), indicating a constant time complexity.', 'The example demonstrates the process of applying binary search to find a specific data point, such as the presence of the key 59 and returning its index.']}