The normal, easy algorithm for searching an array is a
sequential search.
The algorithm looks at item #0, then item
#1, #2, etc, until it finds the target.
This takes up to n
steps, where n is the number of items in the array.
A binary search assumes the array is sorted
(alphabetical or numerical order).
Then it looks in the middle first and
decides whether the target
is in the first half of the list or the last
half. Then it splits that
half of the list in half again. By
splitting the list in half over and over again,
it eventually gets down to a
piece with only 1 item, at that is either the
target or it
isn't.
TRACE the algorithm when it searches for 50, then searches for 70,
then searches for 25.
int nums = {0 , 10 , 20, 30, 40, 50, 60,
70, 80, 90, 100};
int size =
nums.length;
//================================
int
low =
0; //
search for target = 50
int high =
size-1; //
low high middle target ??
nums[middle]
int middle =
-1; //
0
10
//
5
boolean found =
false; // Equal --> found =
true
//=============================
while (high
>= low && !found) // search
for target = 70
{
// low high middle target ??
nums[middle]
middle = (low + high) / 2;
// 0
10
5 70 > 50
-> low=mid+1
if (target <
nums[middle])
//
6 10
8 70 <
80 ->
high=mid-1
{ high = middle - 1;
}
//
6 7 6 70 > 60 ->
low=mid+1
else
if (target > nums[middle]) //
7
7
7 EQUAL
--> found =
true
{
low = middle + 1;
}
//==============================
else
// search for target =
25
{ found =
true;
}
// low high middle target ??
nums[middle]
}
// 0 10
5
25<50 ->
high=mid-1
// 0 4
2 25>20 -> low=mid+1
if
(found) // 3 4
3 25<30 ->
high=mid-1
{ return middle;
}
// 3 2 ... stop because high <
low
else //
found is
false
{ return -1;
}
//==============================