바이너리 = 이진(0,1)
1. 노가다 with T
1) 5개 숫자 중에서 2 찾기
package algo;
import java.util.Arrays; // Arrays 대신 * 입력하면 java.util 패키지에 있는 모든 것 가져올 수 있음
// 2 찾기
public class BSearch01 {
public static void main(String[] args) {
int[] arr = {10,4,1,2,3};
// 1. 정렬 {1,2,3,4,10)
Arrays.sort(arr); // 내가 코드 입력하지 않아도 라이브러리에서 가져다 쓸 수 있음
// 2. 검색 (숫자 2 찾기)
if(arr[2] == 2){
System.out.println("2를 찾았습니다.");
}
if(2 < arr[2]){ // true
System.out.println("2는 작아요.");
if(2 == arr[1]){
System.out.println("2를 찾았습니다.");
}
}
System.out.println("main끝");
}
}2) 5개 숫자 중에서 10 찾기
package algo;
import java.util.Arrays; // Arrays 대신 * 입력하면 java.util 패키지에 있는 모든 것 가져올 수 있음
// 10 찾기
public class BSearch01 {
public static void main(String[] args) {
int[] arr = {10,4,1,2,3};
// 1. 정렬 {1,2,3,4,10)
Arrays.sort(arr); // 내가 코드 입력하지 않아도 라이브러리에서 가져다 쓸 수 있음
// 2. 검색 (숫자 10 찾기)
if(10 == arr[2]){
System.out.println("10를 찾았습니다.");
}
if(10 < arr[2]){ // false
System.out.println("10는 작아요.");
if(10 == arr[1]){
System.out.println("10를 찾았습니다.");
}
}else{
System.out.println("10은 커요.");
if(10 == arr[3]){
System.out.println("10을 찾았습니다.");
}else{
System.out.println("arr[4]번지에 10이 있습니다.");
}
}
System.out.println("main끝");
}
}3) 7개 숫자 중에서 4 찾기
package algo;
import java.util.Arrays;
// 4 찾기
public class BSearch02 {
public static void main(String[] args) {
int[] arr = {10, 4, 1, 2, 3, 8, 6};
// 1. 정렬 {1,2,3,4,6,8,10}
Arrays.sort(arr);
int target = 4;
int mid = arr.length/2; // 3
// 2. 검색
if(target == arr[mid]){
System.out.println(target+"를 찾았습니다.");
}
System.out.println("main끝");
}
}4) 7개 숫자 중에서 11 찾기
package algo;
import java.util.Arrays;
// 4 찾기
public class BSearch03 {
public static void main(String[] args) {
int[] arr = {10, 4, 1, 2, 3, 0, 11};
// 1. 정렬
Arrays.sort(arr); // 0, 1, 2, 3, 4, 10, 11
int target = 11;
int mid = arr.length/2; // 3
// 2. 검색
if(target == arr[mid]){ // 0, 1, 2, [3], 4, 10, 11
System.out.println(target+"를 찾았습니다.");
return; // return 되면 main 종료! main 끝 출력 안됨
}
if (target > arr[mid]){ // true
mid = 5;
}
if (target < arr[mid]){
mid = 1;
}
if(target == arr[mid]){ // 0, 1, 2, 3, 4, [10], 11
System.out.println(target+"를 찾았습니다.");
return;
}
if (target > arr[mid]){
mid = 6;
}
if (target < arr[mid]){
mid = 4;
}
if(target == arr[mid]){ // 0, 1, 2, 3, 4, 10, [11]
System.out.println(target+"를 찾았습니다.");
return;
}
System.out.println("main끝");
}
}
2. 변수정리
1) 나 혼자 실습
package algo;
import java.util.Arrays;
// 4 찾기
public class BSearch04Me {
public static void main(String[] args) {
int[] arr = {9,8,7,6,5,4,3,2,1};
// 1. 정렬
Arrays.sort(arr); // 1,2,3,4,5,6,7,8,9,10,11
int target = 1;
int start = 0;
int end = arr.length-1;
int mid = (end-start)/2+start;
// 2. 검색
if(target == arr[mid]){
System.out.println(target + "을 찾았습니다(1라운드): " + mid + "번지");
return;
}
if (target > arr[mid]){
start = mid+1;
mid = (end-start)/2+start;
}
if (target < arr[mid]){
end = mid-1;
mid = (end-start)/2+start;
}
if(target == arr[mid]){
System.out.println(target + "을 찾았습니다(2라운드): " + mid + "번지");
return;
}
if (target > arr[mid]){
start = mid+1;
mid = (end-start)/2+start;
}
if (target < arr[mid]){
end = mid-1;
mid = (end-start)/2+start;
}
if(target == arr[mid]){
System.out.println(target + "을 찾았습니다(3라운드): " + mid + "번지");
return;
}
if (target > arr[mid]){
start = mid+1;
mid = (end-start)/2+start;
}
if (target < arr[mid]){
end = mid-1;
mid = (end-start)/2+start;
}
if(target == arr[mid]){
System.out.println(target + "을 찾았습니다(4라운드): " + mid + "번지");
return;
}
System.out.println("main끝");
}
}2) with T
package algo;
import java.util.Arrays;
// 4 찾기
public class BSearch05 {
public static void main(String[] args) {
int[] arr = {0, 1, 2, 9, 8, 7, 6, 5, 4, 3, 10}; // 11개 log11 => 3~4회 안에 끝남
Arrays.sort(arr); // {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
int target = 6;
int startIndex = 0;
int endIndex = 10;
int mid = (endIndex-startIndex)/2;
if(target == arr[mid]){
System.out.println(target + "을 찾았습니다(1라운드): " + arr[mid]);
}
startIndex = mid+1;
mid = (endIndex-startIndex)/2+startIndex;
if(target == arr[mid]){
System.out.println(target + "을 찾았습니다(2라운드): " + arr[mid]);
}
endIndex = mid-1;
mid = (endIndex-startIndex)/2+startIndex;
if(target == arr[mid]){
System.out.println(target + "을 찾았습니다(3라운드): " + arr[mid]);
}
}
}
3. 정리 with T
package algo;
import java.util.Arrays;
// 4 찾기
public class BSearch06 {
public static void main(String[] args) {
int[] arr = {0, 1, 2, 9, 8, 7, 6, 5, 4, 3, 10}; // 11개 log11 => 3~4회 안에 끝남
Arrays.sort(arr); // {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
int target = 6;
int startIndex = 0;
int endIndex = 10;
int mid = 0;
// s=0, e=10, m=5 (1회전)
// 0,1,2,3,4,[5],6,7,8,9,10
// s=6, e=10, m=8 (2회전)
// 0,1,2,3,4,5X---,6,7,[8],9,10
// s=6, e=7, m=6 (3회전)
// 0,1,2,3,4,5X---,[6],7,---X8,9,10
mid = (endIndex-startIndex)/2 + startIndex;
if(target == arr[mid]){
System.out.println(target + "을 찾았습니다(1라운드): " + arr[mid]);
}
if(target < arr[mid]){
endIndex = mid-1;
}
if(target > arr[mid]){
startIndex = mid+1;
}
}
}4. while문 정리 with T
package algo;
import java.util.Arrays;
public class BSearch06 {
public static void main(String[] args) {
int[] arr = {0, 1, 2, 9, 8, 7, 6, 5, 4, 3, 10}; // 11개 log11 => 3~4회 안에 끝남
Arrays.sort(arr); // {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
int n = 1;
int target = 6;
int startIndex = 0;
int endIndex = arr.length-1;
int mid = 0;
while (true){
mid = (endIndex-startIndex)/2 + startIndex;
if(target == arr[mid]){
System.out.println(target + "을 찾았습니다(" + n + "라운드): " + arr[mid]);
break;
}
if(target < arr[mid]){
endIndex = mid-1;
}
if(target > arr[mid]){
startIndex = mid+1;
}
n++;
}
}
}
Share article