Created
September 18, 2016 10:40
-
-
Save yssharma/6f61f4fbf267ba630a474f705691f04f to your computer and use it in GitHub Desktop.
Binary search intro for Ayush & Pallavi
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package practice.search; | |
/** | |
* Created by ysharma on 9/18/16. | |
*/ | |
public class BinSearch { | |
public static boolean doIt(int[] arr, int elem){ | |
// return type is boolean .. since we dont have index of elements anyways. we are working on values. | |
int start = arr[0]; | |
int end = arr[arr.length - 1]; | |
while(start <= end){ | |
int midValue = (start + end) / 2; // is a value // | |
System.out.println("start:" + start + ",end:" + end); | |
if(midValue == elem){ | |
return true; | |
} else if (midValue > elem){ // elem is smaller than mid, so look in the part before mid.. | |
// Search before | |
end = midValue - 1; | |
} else { | |
// search after | |
start = midValue + 1; | |
} | |
} | |
return false; | |
} | |
public static int doItOnIndex(int[] arr, int elem){ | |
int start = 0; | |
int end = arr.length - 1; | |
while(start <= end){ | |
int midValue = (start + end) / 2; // is a index // | |
System.out.println("start:" + start + ",end:" + end); | |
if(arr[midValue] == elem){ | |
return midValue; | |
} else if (arr[midValue] > elem){ // elem is smaller than mid, so look in the part before mid.. | |
// Search before | |
end = midValue - 1; | |
} else { | |
// search after | |
start = midValue + 1; | |
} | |
} | |
return -1; | |
} | |
public static int diItRecursive(int[] arr, int elem, int start, int end){ | |
int mid = (start + end) /2; | |
System.out.println("start:" + start + ",end:" + end); | |
if(arr[mid] == elem){ | |
return mid; | |
} else if (arr[mid] > elem){ // elem is smaller than mid, so look in the part before mid.. | |
// Search before | |
return diItRecursive(arr, elem, start, mid - 1); | |
} else { | |
// search after | |
return diItRecursive(arr, elem, mid + 1, end); | |
} | |
} | |
public static void main(String[] args) { | |
int[] arr = {1,2,3,4,5,6,7,8,9,10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20000000}; | |
System.out.println(doIt(arr, 8)); | |
System.out.println(doItOnIndex(arr, 8)); | |
System.out.println(diItRecursive(arr, 8, 0, arr.length-1)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment