Written by Quadrum Lee
February 17, 2020
The one pre-request of binary search- Array should be sorted.
2) Steps to search using binary search algorithm
L = 0 and R = 9
Now we need to find the mid-position of the array where we divide the array into 2 half. We can find it using the equation (L+R) / 2 and takes the flow value of it. So (0+9) / 2 is 4.5 and the flow value is 4.
In here, there are 3 cases can be occurred and let’s take
a is the array,
1. The data you find out is equal to the data in the mid position.
Case 1 :- data == a[mid]
2. The data is less than the data which is in the mid position.
Case 2:- data < a[mid]
3. The data is greater than the data which is in the mid position.
Case 3 :- data > a[mid]
Step 2 –
The data we searched for 59 is passed the condition in case 3. It means 59 is greater than the mid element of the array. So we can say that the data is present on the right subarray. It is because this is a sorted array and all the elements greater than mid(25) must be present to the right of the mid element. Now L becomes Mid+1
L=5 and R=9
Now take the mid-index using (L+R) /2 and it is 7.
Step 3 –
In this time, our searched value 59 is less than the mid-value which is passed the case 2. So data is present to the left of mid (63). Now R becomes Mid – 1 which is 6.
Take the mid index again. (5 + 6) / 2 and the result is 5. Now both L and Mid are 5.
Step 4 –
Now again need to check the cases. 59 is greater than mid-value (45) and fulfil the case 3. If fulfil case 3, L becomes Mid + 1 and the index of it will be 6.
Take the mid index again. (6 + 6) / 2 and the result is 6. Mid is also 5.
Now check the cases and searched data is equal to the Mid value. So it fulfils the case 1 and it is where we should stop the recursion. Now we found the data and we need to return the Mid.
03) What if searched data is not found in the array?
Even there is no searched value in the array, it will take up to step 4.
Now search value 59 is greater than Mid value (58). So L becomes 6+1 and the result is 7. Now, this is the stopping place. If L value becomes greater than R value, it means data is not present here.
04) Implementation of binary search
Cool Gadgets on Amazon 2019 | Cool Amazon ProductsG, 0 Comments Today’s, topic about Cool Gadgets on Amazon 2019. Now, let's go and know about those gadgets in more deep. 01. The orange screwThis is one of the most clever and versatile tools you'll ever...
Is Interstellar Travel Impossible? | Interstellar TravelG, 0 Comments Today's, topic about Interstellar Travel Impossible. Let's go into deep and understand the scientific facts related to this topic. Simply, Is interstellar travel doomed to remain in the...
Smart Retail Technology in IoT – Smart Retail StoresG, 0 Comments Today's topic is about "How IOT Gives Rise to Smart Retail Technology". Simply, I want you to picture your kitchen at home. If you're like most people you can trace many of your...