Binary Search using MATLAB | MATLAB Tutorial

Binary Search using MATLAB | MATLAB Tutorial

 

Binary Search using MATLAB

  • It is most popular & efficient Search algorithm.
  • A search algorithmis an algorithm that retrieves information stored within some data structure.
  • Binary search works only on a sorted set of elements.
  • It is based on Divide & Conquer Algorithm. It divides the array into two & choose the appropriate one according to value at mid index.
  • Binary Search:Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
  • The main advantage of this searching technique is its simplicity & efficiency
  • Time Complexity:
    • Best Case : O (1)
    • Average Case : O (/2)
    • Worst Case : O ()
  • So time complexity of binary searching is O ().

Example

We take an unsorted array for our example.

15 6 1 11 4

And then we will sort the Array

1 4 6 11 15

Best Case

Problem:  Search for Element 6 in given array

1 4 6 11 15

 

  1. Left=1,Right=5

Now Left<Right

Mid=floor(1+5/2)=3

Since arr (3) =find then Print Mid

Average Case

Problem:  Search for Element 11 in given array

1 4 6 11 15

 

  1. Left=1 ,Right=5

Now Left<Right

Mid=floor (1+5/2) =3

Since arr (3) < find then Left=4 Right=5

 

  1. Left=4 ,Right=5

Now Left<Right

Mid=floor (4+5/2) =4

Since arr (4) = find then Print Mid

Worst Case

Problem:  Search for Element 1 in given array

1 4 6 11 15

 

  1. Left=1 ,Right=5

Now Left<Right

Mid=floor (1+5/2) =3

Since arr (3) > find then Left=1 Right=2

 

  1. Left=1 ,Right=2

Now Left<Right

Mid=floor (1+2/2) =1

Since arr (1) < find then Left=2 Right=2

 

  1. Left=2 ,Right=2

Now Left=Right

Mid=floor (2+2/2) =2

Since arr (2) = find then Print Mid

Pseudo-Code

  • We basically ignore half of the elements just after one comparison.
  • 1. Compare x with the middle element.
  • 2. If x matches with middle element, we return the mid index.
  • 3. Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
  • 4. Else (x is smaller) recur for the left half.

MATLAB Code


function [ index ] = Binary_Search(arr,find,l,r)

%arr : Sorted Array of Elements
%find : Element to be found
%l : Left/Start index
%r : Right/End index
%index : Answer array of all indexes where arr(index)==find

index=-1;
while(l<=r) mid=floor((l+r)/2); if(arr(mid)==find) index=mid; break; elseif (arr(mid)>find)
r=mid-1;
else
l=mid+1;
end
end

Output

arr=[5 23 7 34 90 23 11];

arr=sort(arr)

arr =

5     7    11    23    23    34    90

Binary_Search(arr,23,1,7)

ans =

4

Binary_Search(arr,32,1,7)

ans =

-1

Binary_Search(arr,34,1,7)

ans =

6

Binary_Search(arr,7,1,7)

ans =

2


Anushi is pursuing graduation degree in Electronics & Communication from HBTI, Kanpur (Now HBTU). She has a keen interest towards Competitive Programming & loves to solve coding Challenges.