Binary Search in Arrays | Data Structure & Algorithm

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 idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).


Binary search is a fast search algorithm with run-time complexity of Ο(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 looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the sub array reduces to zero.For a binary search to work, it is mandatory for the target array to be sorted.


Algorithm: (Binary Search)
BINARY(DATA, LB, UB. ITEM. LOC)
Here DATA is a sorted array with lower bound LB and upper bound UB, and ITEM is a given item of information. The variables BEG, END and MID denote. respectively, the beginning, end and middle locations of a segment of elements of DATA. This algorithm finds the location LOC of ITEM in DATA or sets LOC = NULL.

1. [Initialize segment variables.]
Set BEG := LB, END := UB and MID = INT((BEG + END)/2).
2. Repeat Steps 3 and 4 while BEG is less than or equal to END and DATA[MID] != ITEM.
3. If ITEM is less than DATA[MID], then:
Set END := MID — 1
Else:
Set BEG := MID + 1
[End of If structure.]
4. Set MID := INT((BEG + END)/2)
[End of Step 2 loop.]
5. If DATA[MID] = ITEM, then
Set LOC := MID.
Else:
Set LOC := NULL.
[End of If structure.]
6. Exit




Binary Search in Arrays Program in C
https://rb.gy/fijv7m