[Algorithm] About Binary Search Algorithm.

 ----------------------------------------------------------------------

Hello, i am GameDeveloperPlayground.

I am a Korean student and I post it for English practise.

I would appreciate pointing out grammar or typos.

----------------------------------------------------------------------

In this post, about Binary search Algorithm.

Binary Search

Data sorting is required to run the binary search algorithm.

Let's look at how algorithm work.

find for number 5 in the array { 1, 3, 4, 5, 7, 8, 10, 20, 60, 100 }.

array[0]	array[1]	array[2]	array[3]	array[4]	array[5]	array[6]	array[7]	array[8]	array[9]
1	3	4	5	7	8	10	20	60	100

First case

Divide array start index and last index value by two.

Check whether the value corresponding to the index is 5 or not if it is 5 or smaller.

( 0 [start index] + 9 [last index] ) /2 = 4.5 (discard the rest) => 4

Since array[4] is = 7. the values not equal.

Array[4] is greater than the value 5. 4~exclude form the dearch until in the list index.

array[0]	array[1]	array[2]	array[3]	array[4]	array[5]	array[6]	array[7]	array[8]	array[9]
1	3	4	5	7	8	10	20	60	100

Second case

(0 [Start index]) + 3 (List index) / 2 = 1.5 => 1

array[1] is 3 , not equal.

array[1] is smaller than 5. it excludes from startindex ~ 1.

array[0]	array[1]	array[2]	array[3]	array[4]	array[5]	array[6]	array[7]	array[8]	array[9]
1	3	4	5	7	8	10	20	60	100

Third case

(2 [start index]) + 3 [last index] ) /2 = 2.5 => 2

array[2] is 4, not equal.

array[2] is smaller than 5, it excludes from startindex ~2.

array[0]	array[1]	array[2]	array[3]	array[4]	array[5]	array[6]	array[7]	array[8]	array[9]
1	3	4	5	7	8	10	20	60	100

Fourth case

(3 [start index])  + 3 [last index]) /2 = 3

array[3] is 5. return the same value index. and end the search.

The time complexity is O(Log N) because retrieve the value by decreasing by half as above.

If the value is not found, return failure value.

Example code

int searchint(int[] intarrays, int index)
{
    int from = 0;
    int to = intarrays.Length - 1;
 
    while (from <= to)
    {
        int mid = (from + to) / 2;
 
        if (intarrays[mid] > index) 
        {
            to = mid - 1;
        }
        else if (intarrays[mid] < index)
        {
            from = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

The terminiation condition of the algorithm.

If the start index(from) is greater than the lst index (to) as in the above code, it terminates.

Thank you.