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.
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
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
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]
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.
34 |
523 |
54 |
32 |
53 |
463 |
43 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
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
First value
at index F1=4
Last value
at index L1=6
Mid value index = (F1+L1)/2= (4+6)/2 = 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
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
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.
#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); }
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)
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"); } } }
0 Comments