Binary Search also known as Algorithmic or binary chop is a searching algorithm that searches for a element in a sorted data structure. Binary search is a searching algorithm that searches the required value by comparing the target value with the middle value of the array.
The following is the algorithm for binary search implementation
Step 0 : Sort the array using any sorting algorithm (I am using bubble sort in the below program)
Step 1 : Initialize first = 0 and last = list.size() - 1
Step 2 : while first < last and the element is not found calculate mid = (first + last) / 2
Step 3 : Compare target value with middle element
Step 4 : if the middle value is greater than the target value then target value lies on the left side of the middle value do goto step 1 with last = mid - 1
Step 5 : if the middle value is lesser than the target value then target value lies on the right side of the middle value do goto step 1 with first = mid + 1
Step 6 : if middle value is equal to the target value return the position of the element as middle.
Step 7 : if first > last and element is not found then the element is not present in the array so display message stating element not found.
Step 8 : Stop.
Time complexity of binary search
You might also be interested in
Singly Linked List
Double Linked List
Linked List in Python
Infix to Prefix Conversion
Infix to Postfix Conversion
Binary Search Tree
The following is the algorithm for binary search implementation
Step 0 : Sort the array using any sorting algorithm (I am using bubble sort in the below program)
Step 1 : Initialize first = 0 and last = list.size() - 1
Step 2 : while first < last and the element is not found calculate mid = (first + last) / 2
Step 3 : Compare target value with middle element
Step 4 : if the middle value is greater than the target value then target value lies on the left side of the middle value do goto step 1 with last = mid - 1
Step 5 : if the middle value is lesser than the target value then target value lies on the right side of the middle value do goto step 1 with first = mid + 1
Step 6 : if middle value is equal to the target value return the position of the element as middle.
Step 7 : if first > last and element is not found then the element is not present in the array so display message stating element not found.
Step 8 : Stop.
Time complexity of binary search
Worst-case performance | O(log n) |
---|---|
Best-case performance | O(1) |
Average performance | O(log n) |
Worst-case space complexity | O(1) |
To know more about Binary Search click Here.
The following is the implementation of Binary Search.
C Program
C++ Program
Singly Linked List
Double Linked List
Linked List in Python
Infix to Prefix Conversion
Infix to Postfix Conversion
Binary Search Tree
Comments
Post a Comment