Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
September 24, 2021 12:47 pm GMT

BINARY SEARCH

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.


Original Link: https://dev.to/shahiscoding/binary-search-45jp

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To