TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Binary Search

Binary Search with Introduction, Asymptotic Analysis, Array, Pointer, Structure, Singly Linked List, Doubly Linked List, Circular Linked List, Binary Search, Linear Search, Sorting, Bucket Sort, Comb Sort, Shell Sort, Heap Sort, Merge Sort, Selection Sort, Counting Sort, Stack, Qene, Circular Quene, Graph, Tree, B Tree, B+ Tree, Avl Tree etc.

<< Back to BINARY

Binary Search

Binary search is the search technique which works efficiently on the sorted lists. Hence, in order to search an element into some list by using binary search technique, we must ensure that the list is sorted.

Binary search follows divide and conquer approach in which, the list is divided into two halves and the item is compared with the middle element of the list. If the match is found then, the location of middle element is returned otherwise, we search into either of the halves depending upon the result produced through the match.

Binary search algorithm is given below.

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

  • Step 1: [INITIALIZE] SET BEG = lower_bound
    END = upper_bound, POS = - 1
  • Step 2: Repeat Steps 3 and 4 while BEG <=END
  • Step 3: SET MID = (BEG + END)/2
  • Step 4: IF A[MID] = VAL
    SET POS = MID
    PRINT POS
    Go to Step 6
    ELSE IF A[MID] > VAL
    SET END = MID - 1
    ELSE
    SET BEG = MID + 1
    [END OF IF]
    [END OF LOOP]
  • Step 5: IF POS = -1
    PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
    [END OF IF]
  • Step 6: EXIT

Complexity

SN Performance Complexity
1 Worst case O(log n)
2 Best case O(1)
3 Average Case O(log n)
4 Worst case space complexity O(1)

Example

Let us consider an array arr = {1, 5, 7, 8, 13, 19, 20, 23, 29}. Find the location of the item 23 in the array.

In 1st step : 

BEG = 0 
END = 8ron
MID = 4 
a[mid] = a[4] = 13 < 23, therefore

in Second step:

Beg = mid +1 = 5 
End = 8
mid = 13/2 = 6  
a[mid] = a[6] = 20 < 23, therefore;

in third step:

beg = mid + 1 = 7 
End = 8 
mid = 15/2 = 7
a[mid] = a[7] 
 a[7] = 23 = item; 
therefore, set location = mid; 
The location of the item will be 7.

Binary Search

Binary Search Program using Recursion

C program

#include<stdio.h>
int binarySearch(int[], int, int, int);
void main ()
{
	int arr[10] = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};
	int item, location=-1; 
	printf("Enter the item which you want to search ");
	scanf("%d",&item);
	location = binarySearch(arr, 0, 9, item);
	if(location != -1) 
	{
		printf("Item found at location %d",location);
	}
	else
	{
		printf("Item not found");
	}
} 
int binarySearch(int a[], int beg, int end, int item)
{
	int mid;
	if(end >= beg) 
	{	
		mid = (beg + end)/2;
		if(a[mid] == item)
		{
			return mid+1;
		}
		else if(a[mid] < item) 
		{
			return binarySearch(a,mid+1,end,item);
		}
		else 
		{
			return binarySearch(a,beg,mid-1,item);
		}
	
	}
	return -1; 
}

Output:

Enter the item which you want to search 
19 
Item found at location 2

Java

import java.util.*;
public class BinarySearch {
public static void main(String[] args) {
	int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};
	int item, location = -1;
	System.out.println("Enter the item which you want to search");
	Scanner sc = new Scanner(System.in);
	item = sc.nextInt();
	location = binarySearch(arr,0,9,item);
	if(location != -1)
	System.out.println("the location of the item is "+location);
	else 
		System.out.println("Item not found");
	}
public static int binarySearch(int[] a, int beg, int end, int item)
{
	int mid;
	if(end >= beg) 
	{	
		mid = (beg + end)/2;
		if(a[mid] == item)
		{
			return mid+1;
		}
		else if(a[mid] < item) 
		{
			return binarySearch(a,mid+1,end,item);
		}
		else 
		{
			return binarySearch(a,beg,mid-1,item);
		}
	
	}
	return -1; 
}
}

Output:

Enter the item which you want to search 
45 
the location of the item is 5

C#

using System;
				
public class LinearSearch
{
	public static void Main()
	{
	int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};
	int location=-1; 
	Console.WriteLine("Enter the item which you want to search ");
	int item = Convert.ToInt32(Console.ReadLine());
	location = binarySearch(arr, 0, 9, item);
	if(location != -1) 
	{
		Console.WriteLine("Item found at location "+ location);
	}
	else
	{
		Console.WriteLine("Item not found");
	}
} 
public static int binarySearch(int[] a, int beg, int end, int item)
{
	int mid;
	if(end >= beg) 
	{	
		mid = (beg + end)/2;
		if(a[mid] == item)
		{
			return mid+1;
		}
		else if(a[mid] < item) 
		{
			return binarySearch(a,mid+1,end,item);
		}
		else 
		{
			return binarySearch(a,beg,mid-1,item);
		}
	
	}
	return -1; 

	}
}

Output:

Enter the item which you want to search 
20 
Item found at location 3

Python

def binarySearch(arr,beg,end,item):
    if end >= beg:
        mid = int((beg+end)/2)
        if arr[mid] == item :
            return mid+1
        elif arr[mid] < item : 
            return binarySearch(arr,mid+1,end,item)
        else: 
            return binarySearch(arr,beg,mid-1,item)
    return -1
    

arr=[16, 19, 20, 23, 45, 56, 78, 90, 96, 100];
item = int(input("Enter the item which you want to search ?"))
location = -1; 
location = binarySearch(arr,0,9,item);
if location != -1: 
    print("Item found at location %d" %(location))
else: 
    print("Item not found")

Output:

Enter the item which you want to search ? 
96 
Item found at location 9 

Enter the item which you want to search ? 
101 
Item not found

Binary Search function using Iteration 

int binarySearch(int a[], int beg, int end, int item)
{
	int mid;
	while(end >= beg) 
	{	
		mid = (beg + end)/2;
		if(a[mid] == item)
		{
			return mid+1;
		}
		else if(a[mid] < item) 
		{
			beg = mid + 1;
		}
		else 
		{
			end = mid - 1; 
		}
	
	}
	return -1; 
}

Next TopicBubble Sort




Related Links:

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf