Binary Search Algorithm
Binary Search Algorithm is a fast Searching Algorithm with run-time complexity of O(log n). This search algorithm works on the principal of divide and conquer rule and the data should be on sorted form for the algorithm to run properly.
Binary Search Algorithm looks for a particular item by comparing the middle most item of the collection. The index of item will return back if a match is found. If the middle item is greater than item, then the item will search in the sub-array to the left of the middle item. Otherwise, the item will search in the sub-array to the right of the middle item. Finally, this process will continue on the sub-array as well until the size of the sub-array reduces to zero and the final result appears.
- Drawing Tool
- Binary Search Algorithm is simple and easy to understand.
- People can sort large number of data in a short period of time using Binary Search Algorithm.
- Easy to use and can be easily operated by beginners.
- It is fast and efficient to use.
- The list of array must be in a sorted array.
- the list can be on both Ascending or Descending order.
Things To Know
- You have to install a programming language like java or python.
- The user must have basic know of Array and some techniques of sorting.
Implementation of Binary Search Algorithm
In binary search algorithm, the elements or values in the array must compulsory in sorting order. The sorted array is given to us. And then, let us search the location of value 6 using binary search algorithms. Let us determine the location and learn the process of binary search using pictorial example.
Figure 1: Binary Search (List of Array in sorted form)
At first, With given formula the half part of array is found:
Mid = low+(high-low)/2
Then, mid= 0+ (9-0)/2 = 4 (integer value of 4.5 is 4). So, the mid value of the array is 4.
Figure 2: Binary Search (Mid Value of Array)
After finding the middle value, the value located at 4 is 5 and it is compared with the search value 6. The value didn’t match because the search value is greater than 5, so the required search value must be in upper portion.
Figure 3: Binary Search (finding next mid value)
Now, we must change the low value to middle value
Then, low = mid + 1
Mid = low + (high-low)/2
Mid = 7
The new middle value is 7. So the new value containing in location 7 is compared with search value 6.
Figure 4: Binary Search (Value Stored)
The value stored in location 7 where the value is 8 did not match with the search vale 6 but as in comparison, the search value is less than the located value. So, the value must be in lower part from the location.
Figure 5: Binary Search (Remaining value Compare)
Here, the mid value is calculated again. The middle value is 5.
Figure 6: Binary Search (Searched value index)
The value stored in location 5 is compared with the targeted value and it is perfect match.
Figure 7: Binary Search (output)
Finally, at last the value is found in location 5.
- 1: Start
- 2: Create a variable to store the first and last value in low and high position respectively.
- 3: If lower value is smaller than high value then Go to step 4 else Go to step 13.
- 4: Find the Middle Value.
- 5: If middle value is Equal to binary search key then Go to step 6 else Go to step 7.
- 6: Display the output or message.
- 7: If middle value is greater than binary search key then Go to step 8 otherwise Go to step 9.
- 8: Replace the lower value position by mid-1.
- 9: If middle value is less than binary search key then Go to step 10 otherwise Go to step 11.
- 10: Replace the lower value position by mid+1.
- 11: Replace the higher value position by mid-1 and Go to step 9.
- 12: Display the output or message
- 13: End
Flow chart of Binary search Algorithm