Binary search Algorithm in data structure and C++
Binary search: if the items in an array are in some order (ascending or descending) then we can obtain much better performance with an algorithm called binary search. In binary search, we first compare the KEY with the items in the middle position of the array. If it is matches, the search process is terminated with the current location (middle+1) from where the value is found. If the key is less than middle key, then the sought item must be searched in the lower half of the array, otherwise the sought item must be searched in the upper half of the array so we repeat the search procedure on the lower or upper half of the array with updated starting and terminating indexes. Algorithm for binary search Step 1: IF(LENGTH=0) THEN (i) output"array is empty" (ii) Exit Else (a) Initialize: start=0, end= LENGTH-1 (b) While ( start<=end) DO middle=(start+end)/2 Step 2: IF (KEY=ARRAY[Middle]) then a. Location=middle+1 b. found=1 c. break Else if(KEY<ARRAY[middle