Basically, any search algorithms would not have Syntax as such but will follow a flow i.e. Flowchart or an Algorithm steps to implement.
Step 1: First, we need to find the middle element of the array
Step 2: Then, start comparing the middle element with the value which is being searched for i.e. key element
- If the key element is less than that of the middle element, start searching in the left half of the array
- If the key element is more than that of the middle element, start searching in the right half of the array
- If the key element is equal to the middle element, return the index of the middle element
Step 3: Continue the above steps until there is a single element left
Step 4: If the key element is not found, then return -1
To understand the above algorithm in a better way, we shall take an example.
Input array: 2 4 6 8 10 12 14 16 18 20 22
Key element: 16
- Now, let us check for the middle element of the array, i.e. 12
- Will compare 12 with 16: As 16>12, we shall ignore the left part and start searching the right half.
- So, array will be 14 16 18 20 22
- Now, the middle element will be 18.
- Let us compare 18 with 16, As 16<18, we shall ignore the right half and go with the left part.
- So, array will have only two elements i.e 14, 16
- As there are only two elements left in the array, we shall go with the middle element as 14.
- Let us compare now, 16>14, only the right part of the array is considered and the left part is ignored.
- Now, we are left with a single element in the array i.e. 16.
- Compare key element with array element now, 16=16, which means the key element is found As seen in the above example, very few comparisons were done to find the key element.
Following are the examples are given below:
Here you can see that the above example which we had solved manually, have given the same input array for the program and the output is as required.
Binary Search Algorithm in Iterative manner
With the input array given, and the key element to be searched, if there is no value available, it will return -1 or null as provided.
Efficiency of Binary Search Algorithm
- Time complexity of Binary search is O(log2n) where n=no. of elements in the array.
- This time complexity is far better than Linear Search, which actually has a time complexity of O(n).
- Binary search works directly on the original array without creating any copies.
- As Binary search needs a sorted array, and hence the time complexity of O(nlogn) is applicable.
- If the array is small in length, then a brute force algorithm can be applied as a better approach.