Scribd
Upload
4 views2 pages

Algo. Lab#3 Binary Search Algorithm

The document describes the binary search algorithm, which is an efficient search method with a time complexity of O(log n) that requires sorted data. It outlines the steps for implementing the algorithm and provides a Java code example for searching a target value in a sorted array. The document emphasizes the divide and conquer principle used in binary search.

Uploaded by

solimano699
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

Algo. Lab#3 Binary Search Algorithm

The document describes the binary search algorithm, which is an efficient search method with a time complexity of O(log n) that requires sorted data. It outlines the steps for implementing the algorithm and provides a Java code example for searching a target value in a sorted array. The document emphasizes the divide and conquer principle used in binary search.

Uploaded by

solimano699
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Level 2 | Algorithms | Lab 3

Binary Search Algorithm


Binary search is a fast search algorithm with a run-time complexity Ο (log n).
This search algorithm works on the principle of divide and conquer. For this
algorithm to work properly, the data collection should be in the sorted form.

Binary Search Algorithm:


Given an array 𝐴 of 𝑛 elements with values 𝐴0 , 𝐴1 , 𝐴2 , … , 𝐴𝑛−1 sorted such that 𝐴0 ≤ 𝐴1 ≤ 𝐴2 ≤
⋯ ≤ 𝐴𝑛−1 , and target value 𝐾 , the following subroutine uses binary search to find the index of 𝐾 in 𝐴.
1. Set 𝐿 to 0 and 𝐻 to 𝑛 − 1.
2. If 𝐿 > 𝐻, the search terminates as unsuccessful.
𝐿+𝐻
3. Set 𝑚 (the position of the middle element) to the result of .
2
4. If 𝐾 > 𝐴𝑚 , set 𝐿 to 𝑚 + 1 and go to step 2.
5. If 𝐾 < 𝐴𝑚 , set 𝐻 to 𝑚 − 1 and go to step 2.
6. If 𝐾 = 𝐴𝑚 , the search is done; return 𝑚 .

Binary Search Code:


import [Link].*;

class BinarySearch {

public static void main(String[] args) {

1|Page
Modern Academy - Eng. Noha Ali
Level 2 | Algorithms | Lab 3
int arr[]={2,5,8,12,16,23,38,56,72,91};
int key; // Search Key

int beg=0;
int end= [Link]-1;
int mid= (beg+end)/2;

[Link]("Guess a number ");


Scanner input = new Scanner([Link]);
key=[Link]();

while (beg <= end)


{
if (key == arr[mid])
{
[Link]("Item found at index "+ mid);
break;
}
if (key < arr[mid])
end=mid -1;

else
beg=mid +1;

mid= (beg+end)/2;

}
if (beg > end)
[Link]("Item not found ");
}
}

Output:

Big O of Binary Search Algorithm ∈ O (Log n)

2|Page
Modern Academy - Eng. Noha Ali

You might also like