What will you do if asked to search for an element in an array of integers. As a naive approach you will traverse the element one by one and check each element if it is equal to the to be searched element.
Now thinking in a different way if we are given a sorted array(increasing order) and we are asked to do the same task. What can be done is, we will first divide the array into two halves , low and high using the mid element. Now we compare the element to be searched (assume it to be x) to the element at index=mid. If arr[mid]==x, we get our answer, but if that is not true, we divide the array in two halves the upper half and the lower half. As the array is already sorted, the element will either occur in the lower or upper half of the array, ie , either to the right or left of mid element. We will eliminate the other choice as the element 'x' cannot lie in that interval. For eg.
Given an array={2,4,5,8,9}, and x=4, here n=5 and mid=n/2=2th index. Now arr[2]==5 which is not equal to 4 , therefore we proceed further and eliminate the upper half of the array, i.e ,[mid+1,high] as 4 cannot lie between 8 and 9. And thus we move to lower half.
Now once we have chosen the half we need to move into, apply the steps again, taking low=low,high=mid-1, mid=(low+high)/2, and repeat the steps until you find the number or the array could not be further divided into halves.
The time complexity for the algorithm is O(log N) as it divides the array into halves and eliminated the other half.
The algorithm can be found below:
Now thinking in a different way if we are given a sorted array(increasing order) and we are asked to do the same task. What can be done is, we will first divide the array into two halves , low and high using the mid element. Now we compare the element to be searched (assume it to be x) to the element at index=mid. If arr[mid]==x, we get our answer, but if that is not true, we divide the array in two halves the upper half and the lower half. As the array is already sorted, the element will either occur in the lower or upper half of the array, ie , either to the right or left of mid element. We will eliminate the other choice as the element 'x' cannot lie in that interval. For eg.
Given an array={2,4,5,8,9}, and x=4, here n=5 and mid=n/2=2th index. Now arr[2]==5 which is not equal to 4 , therefore we proceed further and eliminate the upper half of the array, i.e ,[mid+1,high] as 4 cannot lie between 8 and 9. And thus we move to lower half.
Now once we have chosen the half we need to move into, apply the steps again, taking low=low,high=mid-1, mid=(low+high)/2, and repeat the steps until you find the number or the array could not be further divided into halves.
The time complexity for the algorithm is O(log N) as it divides the array into halves and eliminated the other half.
The algorithm can be found below:
- Set Low to 0 and High to n − 1.
- If Low > High, the search terminates as unsuccessful.
- Set mid (the position of the middle element) to the floor (the largest previous integer) of (Low + High) / 2.
- If arr[mid] < X, set Low to mid + 1 and go to step 2.
- If arr[mid] > X, set High to mid – 1 and go to step 2.
- Now arr[mid] = X, the search is done; return mid.
Note: The code for the same can be iterative as well as recursive. If you need more knowledge or code for the same, contact me. :)
This summarizes Binary Search . I hope this benefits you!!
Subscribe to the blog for more updates! Good Luck!!
~~Cheers!!
No comments:
Post a Comment