Binary Search || Why and Where to Use || In Different Programming Languages 2023


 

Binary Search

The Linear Search algorithm is suitable for small group of data .It would be 

impossible in practice if we were searching through a list consisting of thou-

sands of names, as in a telephone book. But if the names are arranged 

alphabetically, like they are in phone books, we can apply a powerful 

algorithm called binary search.

 

Binary Search Concept

To locate element x in sorted array A, 1st x is compared with middle 

element, if two are equal search is successful, If the two are not equal 

comparing the value of x with middle element narrows the either to the 

lower sub array or upper sub array. Repeating the same technique over 

and over on progressively smaller sub arrays advances the search.  

Process terminates either when a match occurs or when search is 

narrowed down to a sub array which contains no elements.


Case 1

A match occurs. The search is complete and midValue is the index 

that locates the target.

                    If (midValue = target)                            

                    Then

                    Match Found

                    End Algorithm


Case 2

Target value is below midvalue, hence the lower sub list must be 

used to continue the search. Move the last index (last = mid) to the 

end of the sub list.

If (target < midvalue) THEN                                                           

reposition last to mid

search sublist                                                                                

arr[first]…arr[mid-1]

Case 3

Target value is above midvalue, hence the upper sub list must be 

used to continue the search. Move the last index (first= mid+1) 

to the end of the sub list.


if (target > midvalue)                  

reposition first to mid+1

search sub list arr[mid+1]…arr[last-1]


Binary Search Algorithm

Input: A sorted Array A and the element ITEM  to be found

Output: The existence or otherwise of the element under consideration.

DATA= [1, 2, 3, 4, 5, 6, 7]

ITEM=x;

BEGIN: = BN   END: =EN

MID: = INT ((BN + EN)/2) (INT me an Integer (Whole Number))

WHILE (BN<=EN) AND (DATA [MID] ≠ ITEM)

                        IF ITEM < DATA [MID]

                            EN: = MID-1

                        ELSE

                           BN: =MID +1

                           MID: =INT ((BN+EN)/2)

                                    END-WHILE

IF (DATA [MID] =ITEM) THEN

                        Number is found!!

 ELSE

                        Not Exist

END Algorithm          


Binary Search Property

  • It is easy to implement.
  • It can be applied only on sorted arrays.
  • It has less number of comparisons.
  • It is better for small inputs as well as for long inputs.


Binary Search Tracing

Unsorted Form

34

523

54

32

53

463

43

0

1

2

3

4

5

6


         
Sorted Form
                                             

32

34

43

53

54

463

523

0

1

2

3

4

5

6

                                               
                                                         

 

Scenario 1:

Let target value 463

First value at index F1=0

Last value at index L1=6

Mid value index = (F1+L1)/2=3


Since target = 463 > mid = 53, step 2 searches the upper sub list with 

F1 = 4 and L1 = 6.

First value at index F1=4

Last value at index L1=6

Mid value index = (F1+L1)/2= (4+6)/2 = 5


Since target = middle value = 463, a match is found at index mid = 5. 


Scenario 2:

Let target value 34.

First value at index F1=0

Last value at index L1=6

Mid value index = (F1+L1)/2=3


Since target = 34 < Middle value = 53, step 2 searches the lower sub list 

with F1 = 0 and L1 = 2.

First value at index F1=0

Last value at index L1=2

Mid value index = (F1+L1)/2= (4+6)/2 = 1


Since target = middle value = 34, a match is found at index mid = 1. 


Suppose the targeting value is 21 at what index value exist? (Same 

Question rise in linear search)

The binary search attribute makes sure that the search space is effectively 

divided in half with each comparison, resulting in a linear time complexity

of O (log n)where "n" is the collection's element count. Compared to a 

linear search (O (n)), where each element is verified individually, this is 

far more efficient.The array or list should be insorted order, which is the 

only draw back.

 

Program in Different Language


C++

#include<iostream>
using namespace std;
void Binary(int arr[],int size,int x)
{
      int first=arr[0];
      int last=arr[size];
      int middle=(first+last)/2;
      while(first<=last)
      {
        if(arr[middle]==x)
        {
           cout<<"found"<<endl;
           break;
        }
        else if(x>arr[middle])
        {
           first=middle+1;
        }
        else if(arr[middle]>x)
        {
           last=middle-1;
        }
        middle=(first+last)/2;
      }
}
int main() {   int arr[]={1,2,3,4,5,6,7};   int size=sizeof(arr)/sizeof(arr[0]);   Binary(arr,size,31); }

Python

        def binary_search(arr, x):
        first = 0
        last = len(arr) - 1
       
while first <= last:         middle = (first + last) // 2         if arr[middle] == x:         return "Found"         elif x > arr[middle]:         first = middle + 1         else:         last = middle - 1         return "Not Found"         arr = [1, 2, 3, 4, 5, 6, 7]         x = 6         result = binary_search(arr, x)         print(result)

 
Java

public class BinarySearch {
   
public static void main(String[] args) {
       
int[] arr = {1, 2, 3, 4, 5, 6, 7};         int x = 6;         int first = 0;         int last = arr.length - 1;         int middle;         while (first <= last) {             middle = (first + last) / 2;             if (arr[middle] == x) {                 System.out.println("Found");                 break;             } else if (x > arr[middle]) {                 first = middle + 1;             } else if (arr[middle] > x) {                 last = middle - 1;             }         }
       
if (first > last) {            System.out.println("Not Found");         }     } }

Post a Comment

0 Comments