if we're luckycurin may already be pointing to the desired itemso we first check if this is true if it iswe've found the item so we return with its indexcurin each time through the loop we divide the range in half eventually it will get so small it can' be divided any more we check for this in the next statementif lowerbound is greater than upperboundthe range has ceased to exist (when lowerbound equals upperbound the range is one and we need one more pass through the loop we can' continue the search without valid rangebut we haven' found the desired itemso we return nelemsthe total number of items this isn' valid indexbecause the last filled cell in the array is nelems- the class user interprets this value to mean that the item wasn' found if curin is not pointing at the desired itemand the range is still big enoughthen we're ready to divide the range in half we compare the value at the current indexa[curin]which is in the middle of the rangewith the value to be foundsearchkey if searchkey is largerthen we know we should look in the upper half of the range accordinglywe move lowerbound up to curin actually we move it one cell beyond curinbecause we've already checked curin itself at the beginning of the loop if searchkey is smaller than [curin]we know we should look in the lower half of the range so we move upperbound down to one cell below curin figure shows how the range is altered in these two situations figure dividing the range in binary search the ordarray class in generalthe orderedarray java program is similar to higharray java the main difference is that find(uses binary searchas we've seen we could have used binary search to locate the position where new item will be inserted this involves variation on the find(routinebut for simplicity we retain the linear search in insert(the speed penalty may not be important becauseas we've seenan average of half the items must be moved anyway when an insertion is performedso insertion will not be very fast even if we locate the item with binary search howeverfor the last ounce of speedyou could change the initial part of insert(to binary search (as is done in the ordered workshop appletsimilarlythe delete(method could call find(to figure out the location of the item to be deleted