This content originally appeared on DEV Community and was authored by Abhishek shah
What is Binary Search and why to use it?
Binary Search is a search algorithm. It is used to efficiently search for position of a particular number in a sorted array, character in an sorted String. It can also be used to search for first occurrences of a element or last occurrence. Most importantly it can only be used in case of sorted arrays or string.
Logic
In the start we calculate the middle position as
int s = 0, e = the length of array or string.
int mid = (s+e)/2;
Now after we have mid we have 3 case at hand.check if the element at the middle is greater or smaller than the element we are searching for (let say its X).
Case 1: arr[mid]>X
Then that means the element after the mid are also greater than X. So we can reduce the array in search from s to mid. So, we do e=mid-1;
Case 2: arr[mid]<X
Then that means the element before the mid are also smaller than X. So we can reduce the array in search from mid + 1 to e. So, we do s=mid+1;
Case 3: arr[mid]==X
When we finally got the position of X.
Here is a code to show how it
int binarySort(int arr[],int X){
int arr=[1,2,3,4,5,6,7,8,9]; // A sorted Array of length n
int s = 0,e = n-1;
while(s<=e){
int mid = (s+e)/2;
if(arr[mid] > X) e = mid - 1;
else if (arr[mid] < X) s = mid + 1;
else return mid;
}
return -1;
}
To Find First Occurrence or Last Occurrence
When we find the position of X we have to new condition for First Occurrence and Last Occurrence.
First Occurrence:
Check if there is the same element present at mid - 1 position if yes then you would have to decrease the search space. in the case of First Occurrence or mid + 1 position in case of Last Occurrence
else{
if(arr[mid-1] != arr[mid] or mid == 0)
return mid;
else
e = mid - 1;
}
Last Occurrence:
Check if there is the same element present at mid + 1 position if yes then you would have to decrease the search space
by making s = mid+1;
else{
if(arr[mid+1] != arr[mid] or mid == n-1)
return mid;
else
s = mid + 1;
}
If you have anything to add do suggest in the comments.
This content originally appeared on DEV Community and was authored by Abhishek shah
Abhishek shah | Sciencx (2021-09-24T12:47:17+00:00) BINARY SEARCH. Retrieved from https://www.scien.cx/2021/09/24/binary-search/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.