Binary search in C++ programming
Hello, friends in this video we will learn about binary search. Binary Search is a searching algorithm that is used to quickly find a value in a sorted sequence of elements and it uses a divide and conquers strategy to find the element.
Binary Search is an efficient search algorithm as compared to linear search because when we look at the time complexity of linear search which is O(n) where ’n’ is the number of elements, the time complexity of the binary search is O(log n) which is way faster than linear search. So now let’s try to understand how binary search works. Suppose this is the array given to us and we are looking for the element 8, So the basic steps that we will follow to perform binary-search are: firstly we can only perform the binary search when the collection of elements given to us is sorted and as we can see the example that we have taken is sorted in ascending order, Next we will divide the search space i.e. the array in two parts using the variables ‘mid’, ‘start’ and ‘end’ where we initialize ‘start’ as zero and ‘end’ as n-1 where n is the number of elements in the array, So in-short we are storing the first index in the variable ‘start’ and the last index of the array in variable ‘end’.
Next, we will calculate the middle index using the ‘start’ and ‘end’ variables and store it in the variable ‘mid’ which would be equal to (start + end)/2 and then we will check the element at the middle index whether it is the element we are looking for if it is not we will check if the value of the element we are looking for is greater than or less than the value of the element at middle index and if the value is greater then we will store the index mid+1 in ‘start’ else if the value is less we will store the index mid-1 in ‘end’ and we will repeat the steps 5,6,7,8,9 until we find the element we are looking for. So let’s implement this to understand what we are doing…read more