Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * it's not recursion implement
- * @param key is a value required to search for
- * @param arr is an array
- * @return the index of the key in sorted arrayList otherwise -1 if not found
- */
- /**assume the array is [3, 0, 0, 0, 0, 0, 0, 0, 0 , 9].
- * 1-lets assume that previous bottom and previous top are probableBottom and probableTop respectively
- * so that we can keep track where should we back if discovering that we are in wrong direction.
- * 2-check that we are in the wrong direction or not,how can we check?
- * actually the array is almost sorted so assume the middle index is 4 that equal 0(arr[4]=0)
- * and key=9 so according to the binary search algorithm it will move to right(9>0)
- * any positive number is more than zero so it will move to right often.
- * so the new start=4+1 and end=9 the array is quite sorted so the key should belong to
- * range [start,end] and if the key is less than start then it will not belong this range ([start,end])
- * so it should go back as he is in wrong direction these can be made if (key<arr[bottom]) then
- * middle=(probablBottom+probablTop)/2;//go back to previous range .you should store the previous top and bottom in
- * each once so when test (key>arr[middle]) you should make probablTop=middle-1
- * and the rest off binary search algorithms is the same
- **/
- public static int search3(Integer key, int [] arr){
- int middle;
- int top=arr.length-1;
- int bottom=0;
- int probablTop=top,probablBottom=bottom;
- int i=1;
- while (top >= bottom) {
- System.out.println(i++);
- middle=(top+bottom)/2;
- if (key<arr[bottom]){
- middle=(probablBottom+probablTop)/2;
- top=probablTop;
- bottom=probablBottom;
- }
- if (arr[middle]==key)
- return middle;
- else if (key>arr[middle]){
- probablTop=middle-1;
- bottom=middle+1;
- }
- else {
- top = middle - 1;
- }
- }
- return -1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement