Finding first or Last occurrence of a number using Binary Search – Coder in Me

Learn Binary Search in a new Way!

Binary search is the most popular method to find or search an element (numbers) from an array (data structure). In Linear search we did only one thing: we start from the beginning and search it through the end. It’s the best method if that required element is in the beginning but for the last element searching, it’s the worst method.

LINEAR SEARCH

e.g.   array of size 10 with a[10]={1,3,4,5,8,9,7,2,1,11}

If we have to search 3 then by linear search algorithm we can search it in only 2 iterations but if we want to search 11 then a number of iteration will be 10 which is very large.

Linear Search Algorithm

Linear_Search(Array a, size n, search_value s){

	for(Int i=0; i<n; i++){
		if(a[i]==s)
			return i;		
	}
}

Due to this reason, we choose a new method that is binary search method.

In Binary search, we search a particular item by comparing the middle most item of the array. If a get a match, then the index of the item is returned. But if the middle item is greater than the item, then the item is searched in sub-array to the right of the middle item otherwise the item is searched in the sub-array to the left of the middle item. This process continues on the sub-array as well until the size of sub-array reduces to zero.

Binary Search Algorithm

// must be sorted array
Binary_Search(Array a, size n, search_value s){
	low=0;
	high=n-1;
	while(low<=high){
		mid=(low+high)/2;
		if(a[mid]<s)
		   low=mid+1;
		else if(a[mid]>s)
		    high=mid-1;
		else if(a[mid]==s)
		 return mid;
	}  
	  return -1;
}

// mid is the answer

You can learn basic binary search from these links:

  1. Binary Search Basic with Example
  2. Recursive Binary Search

Finding first or Last occurrence of a number using Binary Search

Finding first or Last occurrence of a number using Binary Search

in the above array if we apply simple binary search then what will happen let’s discuss.

  1. if the searching value s=6, then how to decide which 6, because it has 4 occurrences at index 2,3,5,9
  2.  if we use binary search algorithm

if  search value s=6;

here  index low=0,  index (size of array-1) high=10

so  mid=5;

the array at mid  index a[5]=6;

and we were searching  6 so the index is 5. Our answer will be 5 but It’s not the first occurrence or last of 6!

a[6]={2,4,10,10,10,18,20}

index    0  1     2    3    4    5     6

if  s=10

low=0; high=6; mid=3;

A[3]=10; which is s so index is 3

Due to repetition we did few modifications  in algorithm, for the first occurrence we will  approach this algorithm

// must be sorted array
Binary_Search_New(Array a, size n, search_value s){
	low=0;
	high=n-1;
        result=-1
	while(low<=high){
		mid=(low+high)/2;
		if(a[mid]<s)
		  	 low=mid+1;
		else if(a[mid]>s) 
			high=mid-1; 
		else if(a[mid]==s) {
		 	result=mid; high=mid-1;}
	}
	return result; 
}

in this algorithm what we did ?

Finding first or Last occurrence of a number using Binary Search

 

we set the value of low=0 and high=size-1; and also we took a variable result and assign -1 as default if number not found in array.

in while loop  we found the mid value form low+high/2

because we have to find 1st occurrence so we checked if the number is in the middle we assign result=mid. but it might happen same number is in that array and it is in the beginning of an array (from 0 index to  mid index.)

Finding first or Last occurrence of a number using Binary Search

Finding first or Last occurrence of a number using Binary Search

For the Last Occurrence we will do the following:

// must be sorted array
Binary_Search_New(Array a, size n, search_value s){
	low=0;
	high=n-1;
        result=-1
	while(low<=high){
		mid=(low+high)/2;
		if(a[mid]<s)
		   low=mid+1;
		else if(a[mid]>s)
		    high=mid-1;
		else if(a[mid]==s)
		 { result=mid; low=mid+1;}
	}
     return ressult;
}

Finding first or Last occurrence of a number using Binary Search

we can check that how these algorithms are working using above examples. Try these! We will continue this in next article till then enjoy coding and say I have a coder in me.

All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. Therefore For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin @coderinme

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.